Rounding and chaining LLL: finding faster small roots of univariate polynomial congruences

DOI10.1007/978-3-642-54631-0_11zbMATH Open1335.11102OpenAlexW197405257MaRDI QIDQ5402971FDOQ5402971

Authors: Jingguo Bi, Jean-Sébastien Coron, Jean-Charles Faugère, Phong Q. Nguyen, Guénaël Renault, Rina Zeitoun 

Publication date: 25 March 2014

Published in: Public-Key Cryptography – PKC 2014 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-54631-0_11

Recommendations

• scientific article; zbMATH DE number 1182510
• An algorithm for finding small roots of multivariate polynomials over the integers
• Finding Small Roots of Bivariate Integer Polynomial Equations: A Direct Approach
• Advances in Cryptology - EUROCRYPT 2004
• A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers

zbMATH Keywords

RSAcomplexityspeedupLLLsmall roots of polynomial equationsCoppersmith's algorithm

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Cited In (7)

• Fast practical lattice reduction through iterated compression
• Revisiting orthogonal lattice attacks on approximate common divisor problems
• Cryptographic applications of capacity theory: on the optimality of Coppersmith's method for univariate polynomials
• Cryptanalysis of the co-ACD assumption
• Cloud-assisted LLL: a secure and efficient outsourcing algorithm for approximate shortest vector problem
• Thrackles: an improved upper bound
• Towards faster polynomial-time lattice reduction

This page was built for publication: Rounding and chaining LLL: finding faster small roots of univariate polynomial congruences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402971)