7 ms·
The output is a giant table of A= g^X mod p where given A you can look up x.
by zmanian 11y ago
The output is a giant table of A= g^X mod p where given A you can look up x.
- caf 11y agoThere'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.
- qopp 11y agoThe 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.
- r0naa 11y agoSounds like my PMATH assignment for this week :-)