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

DOI10.1007/978-3-642-54631-0_11MaRDI QIDQ5402971zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(7)

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

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)