Hacker News Reader

The output is a giant table of A= g^X mod p where given A you can look up x.

There's more to it than that, though - a table that could let you directly look up the discrete log of an arbitrary A would require on the order of 2^1024 entries (for a 1024 bit group).

It's a table specifically of the discrete logs of a large (but tractable) number of small primes. Those discrete logs can be used as the input to a separate stage that can calculate the discrete log of any value in the field.

The paper mentioned in the article shows how a few complex steps reduces to very large polynomial time, most of which can be precomputed given "45 million computer-years", the rest computed on a per-session basis very quickly.

Sounds like my PMATH assignment for this week :-)

Reply on news.ycombinator.com