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: