trial division over a factor base

[Peter Hackman]

Not sure this is the right forum - if not, perhaps the moderator can move the thread.

I am trying to implement the Index Calculus algorithm for discrete logarithms. My program seems to work, but it's slow. Although the Gaussian part
of my program is very crude (where do I post on that topic?) the real bottleneck is the first step, looking for smooth g^d-residues mod P; seems that failures take too much time. So I'd like to know about strategies for dealing with that.

I've encountered the same problem in the context of the Continued Fractions algorithm and was motivated to use an early abort strategy. I realize something similar would work here although I've no idea about the optimal parameters. What else is there? I'd be perfectly satisfied with pointers to the literature.

[R.D. Silverman]

Originally Posted by Peter Hackman

Not sure this is the right forum - if not, perhaps the moderator can move the thread.

I am trying to implement the Index Calculus algorithm for discrete logarithms. My program seems to work, but it's slow. Although the Gaussian part
of my program is very crude (where do I post on that topic?) the real bottleneck is the first step, looking for smooth g^d-residues mod P; seems that failures take too much time. So I'd like to know about strategies for dealing with that.

I've encountered the same problem in the context of the Continued Fractions algorithm and was motivated to use an early abort strategy. I realize something similar would work here although I've no idea about the optimal parameters. What else is there? I'd be perfectly satisfied with pointers to the literature.

Which index calculus method? There are many variations.

Noone today uses trial division on the residues; instead sieves are used.

[fivemack]

Originally Posted by Peter Hackman

Not sure this is the right forum - if not, perhaps the moderator can move the thread.

I am trying to implement the Index Calculus algorithm for discrete logarithms. My program seems to work, but it's slow. Although the Gaussian part
of my program is very crude (where do I post on that topic?) the real bottleneck is the first step, looking for smooth g^d-residues mod P; seems that failures take too much time. So I'd like to know about strategies for dealing with that.

I can't remember where this came from - I think it was on the forum somewhere - but an idea is not to think of looking for smooth g^d-residues, just look for smooth residues anywhere and let the Gaussian part deal with figuring out the values of d.

And then a nice approach is to pick H something like 1+sqrt(p), J=H^2%p, and then look at things (H+c1)(H+c2) for small c1, c2;

(H+c1)(H+c2) = J + c1H + c2(H+c1)

so if you fix c1 you can sieve over c2 values.

[Peter Hackman]

Originally Posted by R.D. Silverman

Which index calculus method? There are many variations.

Noone today uses trial division on the residues; instead sieves are used.

Algorithm 6.4.1 in Crandall-Pomerance. The field is Z/<p>.

[R.D. Silverman]

Originally Posted by Peter Hackman

Algorithm 6.4.1 in Crandall-Pomerance. The field is Z/<p>.

Well, yes. The method exists and is described.


But noone USES this for the reason you have discovered. It is too slow.

Instead, they use 6.4.2 (function field
sieve for GF(p^q), or the more straightforward NFS for GF(p).
They also use Coppersmith's algorithm for GF(2^n). None of these
latter methods use division. They are all sieves.

[jyb]

Originally Posted by fivemack

I can't remember where this came from - I think it was on the forum somewhere - but an idea is not to think of looking for smooth g^d-residues, just look for smooth residues anywhere and let the Gaussian part deal with figuring out the values of d.

And then a nice approach is to pick H something like 1+sqrt(p), J=H^2%p, and then look at things (H+c1)(H+c2) for small c1, c2;

(H+c1)(H+c2) = J + c1H + c2(H+c1)

so if you fix c1 you can sieve over c2 values.

Peter, the method to which fivemack is referring is described in detail in the following two papers. I found them to be very useful and I used this method to implement an index calculus program of my own.

"Discrete Logarithms in GF(p)" by Coppersmith, Odlyzko, and Schroeppel
"Computation of Discrete Logarithms in Prime Fields" by LaMacchia and Odlyzko

These same papers also describe a sieve variant using Gaussian integers, which was apparently important in that it sparked John Pollard's ideas for the Number Field Sieve.

[Peter Hackman]

Thanks. I've ordered the article from my old university, but haven't received it yet. I suppose that sieveing is not exact (logarithms? ignoring small primes?), meaning at least some trial division, albeit on a much smaller set of lists?

Crandall-Pomerance also describe a method of Bernstein's - of any use here?

While I'm at it, a question on the Gaussian step. I use partial factorization of P-1, trialdividing out small primes, up to 10^6, say, and keeping a large cofactor, in the hope of not encountering non-zero non-invertible classes (the first time I do I will revise my routine!). Then Hensel and CRT. A bit slow.

What about fast alternatives?
Wiedemann looks very attractive, but in order not to mess with parametrical soltions I make my system over-determined in the hope of forcing unique solvability modulo (sm)all primes. What alternatives are there, not requiring a monstruous
programming effort?

[R.D. Silverman]

Originally Posted by Peter Hackman

Thanks. I've ordered the article from my old university, but haven't received it yet. I suppose that sieveing is not exact (logarithms? ignoring small primes?), meaning at least some trial division, albeit on a much smaller set of lists?

Crandall-Pomerance also describe a method of Bernstein's - of any use here?

While I'm at it, a question on the Gaussian step. I use partial factorization of P-1, trialdividing out small primes, up to 10^6, say, and keeping a large cofactor, in the hope of not encountering non-zero non-invertible classes (the first time I do I will revise my routine!). Then Hensel and CRT. A bit slow.

What about fast alternatives?
Wiedemann looks very attractive, but in order not to mess with parametrical soltions I make my system over-determined in the hope of forcing unique solvability modulo (sm)all primes. What alternatives are there, not requiring a monstruous
programming effort?

As you are discovering, the LA for DL is much much harder than the LA
for factoring. It must be done modulo order of the group, rather than mod 2.
My choice is to do the LA mod single precision primes not in the factor base
via Lanczos or an adaptation of (mod 2 BL) to mod p. Then use CRT.

It is ugly.