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

Jul 10, 2021
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 \$fcolon [1, n]to[1, n]\$ is a permutation of \$[1, 2, ldots, n]\$ and \$(f(1),ldots,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 \$Napprox 2^{400}\$ by \$n = 47\$ and \$Napprox 2^{800}\$ by \$n = 95\$. Our accelerated strong primal-dual reduction of [GN08] factors integers \$Napprox 2^{400}\$ and \$Napprox 2^{800}\$ by \$4.2cdot 10^9\$ and \$8.4cdot 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.

Go to Source of this post
Author Of this post: