RSA сломали?
От: BlackEric http://black-eric.lj.ru
Дата: 03.03.21 19:42
Оценка: 13 (3)
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
0
. We find sufficiently short lattice vectors by strong primal-dual
reduction of Rn,f . We factor N ≈ 2
400 by n = 47 and N ≈ 2
800 by n = 95. Our accelerated strong
primal-dual reduction of [GN08] factors integers N ≈ 2
400 and N ≈ 2
800 by 4.2 · 109
and 8.4 · 1010
arithmetic operations, much faster then the quadratic sieve QS and the number field sieve NFS
and using much smaller primes pn. This destroys the RSA cryptosystem.


Там 12 страниц математики
https://github.com/BlackEric001
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.