Paper 2021/232

Fast Factoring Integers by SVP Algorithms

Claus Peter Schnorr

Abstract

To factor an integer $N$ we construct $n$ triples of $p_n$-smooth integers $u,v,|u-vN|$ for the $n$-th prime $p_n$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $\mathcal{L}({\mathbf{R}}_{n,f})$ with basis matrix ${\mathbf{R}}_{n,f}\in {\mathbb{R}}^{(n+1)\times (n+1)}$ where $f:[1,n]\to [1,n]$ is a permutation of $[1,2,...,n]$ and $(f(1),...,f(n),N^{\prime }\ln N)$ is the diagonal and (N'\ln p_1, \ldots, N'\ln p_n, N'\ln N) for $N^{\prime }=N^{\frac{1}{n+1}}$ is the last line of ${\mathbf{R}}_{n,f}$. An independent permutation $f^{\prime }$ yields an independent fac-relation. We find sufficiently short lattice vectors by strong primal-dual reduction of ${\mathbf{R}}_{n,f}$. We factor $N\approx 2^{400}$ by $n=47$ and $N\approx 2^{800}$ by $n=95$. 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."