The Math Forum

Search All of the Math Forum:

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

Math Forum » Discussions » Software » comp.soft-sys.matlab

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

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?

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.