June 17, 2021

SpywareNews.com

Dedicated Forum to help removing adware, malware, spyware, ransomware, trojans, viruses and more!

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.