Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits

DOI10.1007/978-3-540-89255-7_25zbMath1206.94072OpenAlexW1490771242MaRDI QIDQ3600388

Alexander May, Mathias Herrmann

Publication date: 10 February 2009

Published in: Advances in Cryptology - ASIACRYPT 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-89255-7_25

zbMATH Keywords

latticessmall rootsfactoring with known bits

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Related Items

Cryptanalysis of an RSA variant with moduli \(N=p^r q^l\), Partial Key Exposure Attack on CRT-RSA, New Attacks on RSA with Moduli N = p r q, Factoring RSA Moduli with Weak Prime Factors, Cryptographic Applications of Capacity Theory: On the Optimality of Coppersmith’s Method for Univariate Polynomials, Cryptanalysis of a quadratic compact knapsack public-key cryptosystem, Improved Cryptanalysis of the Multi-Prime φ - Hiding Assumption, Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors, Using LLL-Reduction for Solving RSA and Factorization Problems, Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme, Towards Optimal Bounds for Implicit Factorization Problem, Partial Key Exposure: Generalized Framework to Attack RSA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic polynomial-time equivalence of computing the RSA secret key and factoring
• Factoring polynomials with rational coefficients
• Improved low-density subset sum algorithms
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• On the oracle complexity of factoring integers
• Finding a Small Root of a Univariate Modular Equation
• Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known
• Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach
• Efficient Factoring Based on Partial Information
• Solving Simultaneous Modular Equations of Low Degree
• Cryptanalysis of RSA with private key d less than N/sup 0.292/
• Advances in Cryptology - EUROCRYPT 2004
• Advances in Cryptology – CRYPTO 2004
• Floating-Point LLL Revisited
• Public Key Cryptography - PKC 2006