**Rounding LLL: Finding Faster Small Roots of Univariate Polynomial Congruences **

*Jingguo Bi and Phong Q. Nguyen*

**Abstract: **In a seminal work at EUROCRYPT '96, Coppersmith showed how to find all small roots of a univariate polynomial congruence in polynomial time:
this has found many applications in public-key cryptanalysis and in a few security proofs.
However, the running time of the algorithm is a high-degree polynomial,
which limits experiments:
the bottleneck is an LLL reduction of a high-dimensional matrix with extra-large coefficients.
We present in this paper a polynomial speedup over Coppersmith's algorithm.
Our improvement is based on a special property of the matrices used by Coppersmith's algorithm,
which allows us to speed up the LLL reduction by rounding.
The exact speedup depends on the LLL algorithm used: for instance, the speedup is quadratic
in the bit-size of the small-root bound if one uses the Nguyen-Stehlé L^2 algorithm.

**Category / Keywords: **public-key cryptography / Coppersmith's Algorithm, Small Roots of Polynomial Equations, LLL, Complexity, Speedup, RSA.

**Date: **received 17 Aug 2013

**Contact author: **pnguyen at di ens fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20130817:205128 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]