Thread Subject:

Elliptic Curve Cryptanalysis Scales More Slowly Than O(n*log(n))

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?

Vaughan Anderson <vaughan.andursen@gmail.com> wrote in message <34d962be-a0a5-44df-8dbe-a61e6b530973@m4g2000pbd.googlegroups.com>...
>
> 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).

Really? I guess when I learned that exp(A*B) is not
equal to exp(A)*exp(B), I was wrong. Learn new
things every day. This new math is so complicated.