mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-10-19, 08:54   #1
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

22·5 Posts
Default 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.
Peter Hackman is offline   Reply With Quote
Old 2009-10-19, 09:57   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-10-19, 10:48   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
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.
fivemack is offline   Reply With Quote
Old 2009-10-19, 13:52   #4
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

22×5 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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>.
Peter Hackman is offline   Reply With Quote
Old 2009-10-19, 14:12   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-10-19, 18:21   #6
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

22·3·7·19 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
jyb is online now   Reply With Quote
Old 2009-10-26, 13:43   #7
Peter Hackman
 
Peter Hackman's Avatar
 
Oct 2007
linköping, sweden

22·5 Posts
Default

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?
Peter Hackman is offline   Reply With Quote
Old 2009-10-26, 18:27   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by Peter Hackman View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sublinear complexity of trial division? yih117 Math 5 2018-02-02 02:49
Mersenne trial division implementation mathPuzzles Math 8 2017-04-21 07:21
P95 trial division strategy SPWorley Math 8 2009-08-24 23:26
Trial division software for Mersenne SPWorley Factoring 7 2009-08-16 00:23
Need GMP trial-division timings ewmayer Factoring 7 2008-12-11 22:12

All times are UTC. The time now is 23:52.

Mon Nov 30 23:52:59 UTC 2020 up 81 days, 21:03, 1 user, load averages: 1.55, 1.49, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.