mersenneforum.org trial division over a factor base
 Register FAQ Search Today's Posts Mark Forums Read

 2009-10-19, 08:54 #1 Peter Hackman     Oct 2007 linköping, sweden 22×5 Posts trial division over a factor base 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.
2009-10-19, 09:57   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 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.

2009-10-19, 10:48   #3
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

33·239 Posts

Quote:
 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.

2009-10-19, 13:52   #4
Peter Hackman

Oct 2007

22·5 Posts

Quote:
 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>.

2009-10-19, 14:12   #5
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by Peter Hackman Algorithm 6.4.1 in Crandall-Pomerance. The field is Z/

.

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.

2009-10-19, 18:21   #6
jyb

Aug 2005
Seattle, WA

34408 Posts

Quote:
 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.

 2009-10-26, 13:43 #7 Peter Hackman     Oct 2007 linköping, sweden 101002 Posts 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?
2009-10-26, 18:27   #8
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post yih117 Math 5 2018-02-02 02:49 mathPuzzles Math 8 2017-04-21 07:21 SPWorley Math 8 2009-08-24 23:26 SPWorley Factoring 7 2009-08-16 00:23 ewmayer Factoring 7 2008-12-11 22:12

All times are UTC. The time now is 16:27.

Sat May 21 16:27:12 UTC 2022 up 37 days, 14:28, 0 users, load averages: 1.29, 1.23, 1.28