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 diophanti
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.
show moreshow less

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Harald Ritter, Carsten Rössner
URN:urn:nbn:de:hebis:30-12628
Document Type:Working Paper
Language:English
Date of Publication (online):2005/07/20
Year of first Publication:1997
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2005/07/20
Source:http://www.mi.informatik.uni-frankfurt.de/research/papers.html ; http://eprint.iacr.org/1997/008
HeBIS PPN:190610786
Institutes:Mathematik
Informatik
Dewey Decimal Classification:510 Mathematik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $