[Resource Topic] 1997/008: Factoring via Strong Lattice Reduction Algorithms

Welcome to the resource topic for 1997/008

Factoring via Strong Lattice Reduction Algorithms

Authors: Harald Ritter, Carsten Roessner


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.

ePrint: https://eprint.iacr.org/1997/008

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .