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] \rightarrow [1,n]$ is a permutation of $[1,2,...,n]$ and $(N f(1),...,N f(n))$ is the diagonal of $\mathbf{R}_{n,f}$. We get an independent fac-relation from an independent permutation $f'$. 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 $N \approx 2^{400}$ and $N \approx 2^{800}$ by $4.2 \cdot 10^9$ and $8.4 \cdot 10^{10}$ arithmetic operations, much faster then the quadratic sieve {\bf QS} and the number field sieve {\bf NFS} and using much smaller primes $p_n$. This destroyes the RSA cryptosystem.