Welcome to the resource topic for 2021/933
Title:
Fast Factoring Integers by SVP Algorithms, corrected
Authors: 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.
ePrint: https://eprint.iacr.org/2021/933
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .