Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

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

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

From: Vaughan Anderson

Date: 18 Dec, 2012 13:11:37

Message: 1 of 2


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?

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

From: John D'Errico

Date: 18 Dec, 2012 16:36:08

Message: 2 of 2

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.

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us