**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: **roessner

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

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

[ Cryptology ePrint archive ]