## Cryptology ePrint Archive: Report 1997/008

**Factoring via Strong Lattice Reduction Algorithms**

*Harald Ritter, Carsten Roessner*

**Abstract: **We address to the problem to factor a large composite number
by lattice reduction algorithms.
Schnorr has shown that under a reasonable number
theoretic assumptions this problem can
be reduced to a simultaneous diophantine
approximation problem. The latter in turn can be solved by finding
sufficiently many l_1--short vectors in a suitably defined lattice.

Using lattice basis reduction algorithms Schnorr and Euchner applied
Schnorrs reduction technique to 40--bit long integers.
Their implementation needed several hours to compute a 5% fraction
of the solution, i.e., 6 out of 125
congruences which are necessary to factorize the composite.

In this report we describe a more efficient implementation using
stronger lattice basis reduction techniques incorporating ideas
of Schnorr, Hoerner and Ritter.
For 60--bit long integers our algorithm yields a complete factorization
in less than 3 hours.

**Category / Keywords: **

**Publication Info: **Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.

**Date: **received June 13th, 1997.

**Contact author: **roessnercs uni-frankfurt de

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

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

[ Cryptology ePrint archive ]