Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Elliptic Curve Cryptanalysis Scales More Slowly Than O(n*log(n))
Replies: 1   Last Post: Dec 18, 2012 11:36 AM

 Messages: [ Previous | Next ]
 Vaughan Anderson Posts: 5 Registered: 12/18/12
Elliptic Curve Cryptanalysis Scales More Slowly Than O(n*log(n))
Posted: Dec 18, 2012 8:11 AM

Why aren't people cracking public key crypto with the Lenstra
algorithm?

The algorithm scales as exp(sqrt(log(n)*loglog(n))), which is a benign
function. Throw away the square root, to get exp(log(n)*log(log(n))),
which reduces to n*log(n).

The discarded square root means that that Lenstra scales *more slowly*
than n*log(n).

This should make it a perfectly workable choice for cryptanalysis,
since n*log(n) is the gold standard for a useful algorithm.

But if Lenstra were used widely internet banking would become useless.

So why doesn't my argument prove that Lenstra scaling can be used to
crack public key crypto?

What did I miss?

Date Subject Author
12/18/12 Vaughan Anderson
12/18/12 John D'Errico