Paper 2021/232
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,uvN$ for the $n$th prime $p_n$. Denote such triple a facrelation. We get facrelations 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 facrelation. We find sufficiently short lattice vectors by strong primaldual 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 primaldual 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.
Note: Revised by the editors on direct request of the author on 20210409."[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."
Metadata
 Available format(s)
  withdrawn 
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 Primaldual reductionSVPfacrelation
 Contact author(s)
 schnorr @ cs unifrankfurt de
 History
 20210605: withdrawn
 20210302: received
 See all versions
 Short URL
 https://ia.cr/2021/232
 License

CC BY