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 .