20091019, 08:54  #1 
Oct 2007
linköping, sweden
20_{10} 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^dresidues 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. 
20091019, 09:57  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
Which index calculus method? There are many variations. Noone today uses trial division on the residues; instead sieves are used. 

20091019, 10:48  #3  
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
Quote:
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. 

20091019, 13:52  #4 
Oct 2007
linköping, sweden
2^{2}·5 Posts 

20091019, 14:12  #5  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,877 Posts 
Quote:
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. 

20091019, 18:21  #6  
Aug 2005
Seattle, WA
2·13·71 Posts 
Quote:
"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. 

20091026, 13:43  #7 
Oct 2007
linköping, sweden
2^{2}·5 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?
CrandallPomerance 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 P1, trialdividing out small primes, up to 10^6, say, and keeping a large cofactor, in the hope of not encountering nonzero noninvertible 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 overdetermined in the hope of forcing unique solvability modulo (sm)all primes. What alternatives are there, not requiring a monstruous programming effort? 
20091026, 18:27  #8  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,877 Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sublinear complexity of trial division?  yih117  Math  5  20180202 02:49 
Mersenne trial division implementation  mathPuzzles  Math  8  20170421 07:21 
P95 trial division strategy  SPWorley  Math  8  20090824 23:26 
Trial division software for Mersenne  SPWorley  Factoring  7  20090816 00:23 
Need GMP trialdivision timings  ewmayer  Factoring  7  20081211 22:12 