Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


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

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
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?



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

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.