Welcome to the resource topic for
**1997/008**

**Title:**

Factoring via Strong Lattice Reduction Algorithms

**Authors:**
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.

**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 .