What's the state of the art in factorization?
sneves at dei.uc.pt
Tue Apr 20 13:03:24 EDT 2010
The state of the art in factorization is the same as for, e.g., the
factorization of RSA-768  --- there haven't been many advances in the
number field sieve algorithm itself. The current effort, as Bernstein
puts it, is in speeding up smoothness detection, as part of the relation
Both the RSA-768 factorization paper and a previous one by the same
authors  try to predict the effort needed for a 1024-bit prediction,
which is estimated to be around 1000 times harder than a 768-bit
modulus.  estimates to number of operations in the RSA768
factorization to be in the ballpark of 2^67 instructions: a thousand
times harder puts this on about 2^77, which puts it in the realm of
doable, but very hard, even for a well funded organization.
We also have to take into account the logistics of doing such a
factorization. Unlike an elliptic curve discrete logarithm computation,
that takes (relatively) negligible storage and communication, the number
field sieve requires massive amounts of data, and the linear algebra
step could become (even more of) a problem.
On 20-04-2010 16:45, Perry E. Metzger wrote:
> I was alerted to some slides from a talk that Dan Bernstein gave a few
> days ago at the University of Montreal on what tools will be needed to
> factor 1024 bit numbers:
> It has been a couple of years since there has been serious discussion on
> the list on this topic, and especially in the light of various technical
> decisions being undertaken on the size of DNS signing keys for high
> valued zones (like root), I was curious as to whether anyone had any
> interesting comments on the state of the art in factorization.
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography