20130712, 01:36  #1 
Jul 2013
1 Posts 
Software for discrete logarithms
I am not sure where this message goes.
I am thinking of implementing a software for performing discrete logarithms over large prime fields, by some advanced algorithms like Index Calculus, Function Field Sieve. I would like to seek an advice if it will be useful to everyone, and if there is a need for such a software when compared to currently existing ones that can handle this problem over large prime field faster. I have used Discrete Logarithm software from http://www.alpertron.com.ar/DILOG.html, which performs PohligHellman algorithm capable of handling problem if the modulus is composite, composed of small prime factors, say < 10^{15}, but is incapable of handling large prime modulus fields. Lakshmi 
20130712, 11:22  #2 
Tribal Bullet
Oct 2004
DD1_{16} Posts 
There is very little available software that can solve this problem. The only public package I know about is GDLOG. Also, the CADONFS project is building a functionfield sieve capability on top of their number field sieve code, and the developers are very responsive if you post to the cadonfsdiscuss mailing list.
People here actually are basically not interested at all in solving general discrete logarithm problems. That's actually a bit surprising given how much interest this forum has in integer factorization. 
20131007, 01:24  #3 
Feb 2005
252_{10} Posts 
See also http://www.cs.toronto.edu/~cvs/dlog/

20131007, 12:15  #4  
Nov 2003
7460_{10} Posts 
Quote:
factorization. There are applications for factoring. There are sets of numbers whose factorization is "interesting" and/or useful. What similar things are there for DL? There are ECDL challenge problems, but NFS is not applicable. 

20131007, 12:17  #5  
Nov 2003
2^{2}·5·373 Posts 
Quote:
While Dl over finite fields is used for breaking DH, DSA, and ElGamal, these crypto primitives are not used to nearly the same extent as RSA. 

20131209, 15:53  #6 
Sep 2002
Database er0rr
3,673 Posts 
We are trying to solve k for , p prime < 2^64, to be used in a sieve. Currently, we are using Pollard's Rho, where has to be a generator of . Is there a fast algorithm for a nongenerator we can use, faster than brute force multiplication and multiplicative order calculation? Last fiddled with by paulunderwood on 20131209 at 15:54 
20131209, 16:13  #7  
Nov 2003
2^{2}·5·373 Posts 
Quote:
generator, then you ask about a fast method for a nongenerator. Please clarify. If alpha is not a primitive root, then Beta might not be in its orbit. (i.e. no solution) PohligHellman should probably work, depending on the factorization of p1. If not, then the choices are: an O(sqrt(p)) method such as Pollard Rho [or Pollard Kangaroo if you run in parallel], or Baby Step/Giant Step OR: While I have never used NFS on a field this small, it may not be too bad. Of course, implementing NFS yields a thundering amount of code. If anyone else has better suggestions I would love to hear about them. 

20131209, 16:26  #8 
Sep 2002
Database er0rr
3,673 Posts 
We have the cases where is a generator for some prime p_{i} covered by Pollard Rho. However, for some prime p_{j}, is not a generator. (In our sieve, is a fixed base.)
Thanks for you pointers, RDS. Will PohligHellman work for a nongenerator  i.e. solve k if is in 's orbit or say "nay" if not? Last fiddled with by paulunderwood on 20131209 at 16:40 
20131209, 16:43  #9 
Feb 2005
2^{2}×3^{2}×7 Posts 
To eliminate obvious cases with no solutions, I suggest first to compute the multiplicative order (by factoring and eliminating its prime divisors as needed) of and test whether . If this congruence does not hold, there are no solutions.

20131210, 01:52  #10  
Jun 2003
1,579 Posts 
Quote:
Even for cases where there is a solution (beta is in alphas orbit) PohligHellman with Pollard rho will be faster (depending on p1 factorization) than Pollard rho by itself. Baby stepGiant step is better than Pollard rho as it is definitive (gives you a yes or no answer) over a range of n but requires significantly more memory. Baby stepGiant step can also be combined with PohligHellman. 

20131216, 20:27  #11 
Sep 2002
Database er0rr
7131_{8} Posts 
Thanks. This is very useful. I can give a tighter condition: where g is the g.c.d. of q and k. Did you mean this?
Last fiddled with by paulunderwood on 20131216 at 20:27 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help with discrete logarithm  pinnn  Information & Answers  43  20210318 15:40 
Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)?  Raman  Factoring  1  20160523 13:44 
Pollard Rho Discrete Log  rogue  Math  6  20120926 11:20 
Discrete logarithm software  Unregistered  Information & Answers  39  20120427 20:08 
On discrete logs  kpatsak  Math  1  20080219 04:44 