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.

By admin