Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
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?
|
|
|
|
