Factoring via strong lattice reduction algorithm : technical report

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

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Harald Ritter, Carsten Rössner
Document Type:Report
Year of Completion:1997
Year of first Publication:1997
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2005/07/20
Issue:May 16, 1997
Page Number:9
First Page:1
Last Page:9
Institutes:Informatik und Mathematik / Mathematik
Informatik und Mathematik / Informatik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoDeutsches Urheberrecht