1. watchA
https://eprint.iacr.org/2021/232
2. whois
Fast Factoring Integers by SVP Algorithms
Claus Peter Schnorr
Abstract: To factor an integer N
we construct n triples of pn-smooth integers u,v,|u−vN| for the n-th prime pn. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice L(Rn,f) with basis matrix Rn,f∈R(n+1)×(n+1) where f:[1,n]→[1,n] is a permutation of [1,2,...,n] and (Nf(1),...,Nf(n)) is the diagonal of Rn,f. We get an independent fac-relation from an independent permutation f′. We find sufficiently short lattice vectors by strong primal-dual reduction of Rn,f. We factor N≈2400 by n = 47 and N≈2800 by n = 95. Our accelerated strong primal-dual reduction of [Gama, Nguyen 2008] factors integers N≈2400 and N≈2800 by 4.2⋅109 and 8.4⋅1010 arithmetic operations, much faster then the quadratic sieve {\bf QS} and the number field sieve {\bf NFS} and using much smaller primes pn
. This destroys the RSA cryptosystem.
Category / Keywords: secret-key cryptography / Primal-dual reduction, SVP, fac-relation