Parallel discrete logs (continues: modular arithmetic)

[CRGreathouse]

I'm working on a problem that involves calculating many discrete logarithms in GF(p): given n and an odd prime p, either find a k with 2^k\equiv n\pmod p or return "failure" if no such k exists. Now there are many algorithms for computing discrete logarithms, some of which are designed for many queries: precalculations are done on a given p which allow queries for each n to be done quickly.

I have the opposite problem: one n value (say, -2131) but many odd primes p. In particular, I have been using the odd primes up to 10 million to 60 million. (I hope to increase this range dramatically, but current methods are too slow.)

Because I'm using sequential primes, I could if desired factor p-1 (or other terms) quickly with a sieve. Certain other calculations that are conventionally 'hard' become easy with such small moduli. In particular, since all numbers I use fit into a single machine word, multiplication is fast relative to its normal cost in multiprecision.

Further, the problem I'm working on has tolerance for gaps. A rare response of "unknown" from the algorithm would not be harmful. Each prime p for which I compute the discrete log contributes 'value' for the problem inversely proportional to the order of 2 mod p, so doubling the speed at the cost of 10% "unknown" values would be worthwhile.

Being wholly ignorant of the subtleties of the various algorithms I've seen, I thought to implement the baby step giant step algorithm to see how long it takes. The memory shouldn't be an issue, I hope -- for primes under a billion it should fit in my 128 kB L1 cache. (Unless I have 64 kB, in which case perhaps it is an issue.) The number field sieve methods seem to be (1) hard to code and (2) too slow for small primes, but the other ones I'm not sure about. Does anyone have experience here?

 

[CRGreathouse]

OK, I've implemented a basic version of the baby-step giant-step algorithm. It was actually a bit more complicated than I'd hoped: while it's a simple thing of itself, making it run in my program required a number of other changes.

I've set it to run on a huge problem size: the primes up to 500 million. This means 26 million discrete logarithm problems with prime moduli of 8-9 digits. Fortunately the lookup tables aren't bad at all, 90 kB in the worst case.

I inadvertently left the 'sanity checks' in the program, which check the discrete log after calculating it. While it will slow the program down slightly, it'll be nice to know it worked properly if that doesn't fire.


Any thoughts from someone who's actually used or coded some kind of discrete log program would be welcome. Heck, any comments would be appreciated period -- sometimes a second look can tell a lot, and I can miss obvious stuff. ;)