- #1
- 2,844
- 0
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 [itex]2^k\equiv n\pmod p[/itex] 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?
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?