**Fast Factoring Integers by SVP Algorithms**

*Claus Peter Schnorr*

**Abstract: **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.

**Category / Keywords: **public-key cryptography / Primal-dual reduction, SVP, fac-relation

**Date: **received 1 Mar 2021, last revised 9 Apr 2021

**Contact author: **schnorr at cs uni-frankfurt de

**Available format(s): **PDF | BibTeX Citation

**Note: **Revised by the editors on direct request of the author on 2021-04-09.
"[We] revised the diagonal of the basis matrix $\mathbf{R}_{n,f}$ to minimise its determinant. The smaller determinant accelerates the factoring algorithm and minimises the numbers of the computations."

**Version: **20210409:151242 (All versions of this report)

**Short URL: **ia.cr/2021/232

[ Cryptology ePrint archive ]