# Fast Factoring Integers by SVP Algorithms, by Claus Peter Schnorr

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 \$(f(1),…,f(n), N’ln N)\$ is the diagonal and (N’ln p_1, ldots, N’ln p_n, N’ln N) for \$N’=N^{frac{1}{n+1}}\$ is the last line of \$mathbf{R}_{n,f}\$. An independent permutation \$f’\$ 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 \$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 and the number field sieve and using much smaller primes \$p_n\$. This destroys the RSA cryptosystem.