Can someone explain what "breaking a prime" means? What is the output after your year of computation?

 Assuming they are using an index-calculus attack, the output is the discrete logarithms of a set of small primes. (But who knows, they may have much better attacks.)This is how that attack works. You generate a set of small primes called the base primes:`````` 2, 3, 5, 7, 11, ... `````` Then you generate powers of p which all factor in only the base primes. This creates a set of linear equations, which can be solved to find the discrete logarithm of all base primes.This was all pre-computation. After this, to find the discrete logarithm of x, you generate powers of x until it factors in the set of base primes. Once that is found, calculating the logarithm is easy.This requires a trade-off: the larger the set of base primes, the longer the first step takes, but the faster the second step is.
 To clarify, I made an error: you generate powers of g (or just any group element whose discrete log you know), not p.
 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 :-)

Search: