Paper 2021/933

Fast Factoring Integers by SVP Algorithms, corrected

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\colon [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 $N\approx 2^{400}$ by $n = 47$ and $N\approx 2^{800}$ by $n = 95$. Our accelerated strong primal-dual reduction of [GN08] 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Primal-dual reductionSVPfac-relation
Contact author(s)
schnorr @ cs uni-frankfurt de
History
2021-07-09: received
Short URL
https://ia.cr/2021/933
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/933,
      author = {Claus Peter Schnorr},
      title = {Fast Factoring Integers by SVP Algorithms, corrected},
      howpublished = {Cryptology ePrint Archive, Paper 2021/933},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/933}},
      url = {https://eprint.iacr.org/2021/933}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.