Paper 2021/232

Fast Factoring Integers by SVP Algorithms

Claus Peter Schnorr

Abstract

To factor an integer $$ we construct $$ triples of $$-smooth integers $$ for the $$-th prime $$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $$ with basis matrix $$ where $$ is a permutation of $$ and $$ is the diagonal and (N'\ln p_1, \ldots, N'\ln p_n, N'\ln N) for $$ is the last line of $$. An independent permutation $$ yields an independent fac-relation. We find sufficiently short lattice vectors by strong primal-dual reduction of $$. We factor $$ by $$ and $$ by $$. Our accelerated strong primal-dual reduction of [Gama, Nguyen 2008] factors integers $$ and $$ by $$ and $$ arithmetic operations, much faster then the quadratic sieve and the number field sieve and using much smaller primes $$. This destroys the RSA cryptosystem.

Note: Revised by the editors on direct request of the author on 2021-04-09."[We] revised the diagonal of the basis matrix $$ to minimise its determinant. The smaller determinant accelerates the factoring algorithm and minimises the numbers of the computations."