Solving Simultaneous Modular Equations of Low Degree

DOI10.1137/0217019zbMath0642.94029DBLPjournals/siamcomp/Hastad88OpenAlexW2085856764WikidataQ56959254 ScholiaQ56959254MaRDI QIDQ3783957

Johan T. Håstad

Publication date: 1988

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/51a80f6eafb9d366bf729a44acff42313eaec041

zbMATH Keywords

complexitypolynomial congruencesinsecuritycomputational number theoryRSA cryptosystemalgebraic coding theorylattice algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Congruences; primitive roots; residue systems (11A07)

Related Items (20)

Meta-heuristic approaches to solve shortest lattice vector problem ⋮ Mathematical problems in cryptology ⋮ A generalized attack on RSA type cryptosystems ⋮ Factoring RSA Moduli with Weak Prime Factors ⋮ Solving low-density multiple subset sum problems with SVP oracle ⋮ On the Improvement of the BDF Attack on LSBS-RSA ⋮ How to fake an RSA signature by encoding modular root finding as a SAT problem ⋮ On the optimality of lattices for the Coppersmith technique ⋮ A natural lattice basis problem with applications ⋮ Cryptanalysis of RSA for a special case with \(d > e\) ⋮ Using LLL-Reduction for Solving RSA and Factorization Problems ⋮ Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits ⋮ Solving Systems of Modular Equations in One Variable: How Many RSA-Encrypted Messages Does Eve Need to Know? ⋮ Randomness Reuse: Extensions and Improvements ⋮ GNUC: a new universal composability framework ⋮ Simplified High-Speed High-Distance List Decoding for Alternant Codes ⋮ Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits ⋮ The multi-dimension RSA and its low exponent security ⋮ Efficient and tight oblivious transfer from PKE with tight multi-user security ⋮ Forty years of attacks on the RSA cryptosystem: A brief survey

This page was built for publication: Solving Simultaneous Modular Equations of Low Degree