20140708, 13:55  #1 
Jul 2014
13 Posts 
GDLOG discrete logarithm usage example
Hello,
I'm trying to solve a discrete logarithm problem using the GDLOG software for a university course about computer security. My GDLOG job file looks like this: p:933190321157583528661602718523 q:466595160578791764330801359261 g:7 t:709787689553880977598302546337 p1Fact:[2 466595160578791764330801359261] lc0Fact:[3 13 241 381301] I'm trying to find the solution to the equation g^x mod p = t mod p p is on 100 bits I know this problem is small enough to be solved with other software, but I still want to use GDLOG, because later I must use larger numbers (on 256 bits). When I run GDLOG it gets stuck (I think) at the sieve process: Logarithm of the 709787689553880977598302546337 to the 7 is 189157217769891068621649792289. Checking result: wrong Then it repeats the process and outputs the same message. I've attached a sample of the log file. What am I doing wrong? Thank you 
20140708, 20:57  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 
Quote:
but 7 is the logarithm BASE (i.e. g). Try computing instead, 7^189157217769891068621649792289 Also, WT<blank> is "q"???? I know nothing about the GDLOG software. Please Describe it. Give a definition for its input (format), its output format and the method(s) that it uses internally. 

20140708, 21:11  #3 
"Forget I exist"
Jul 2009
Dumbassville
2×5×839 Posts 

20140708, 22:27  #6 
(loop (#_fork))
Feb 2006
Cambridge, England
2·7·461 Posts 
Using magma, g is a primitive root mod p; we have p=2q+1 for q as given, but that's not particularly important.
Log(g,t) is 379721093484885118231722056 which doesn't look like 189157217769891068621649792289 at all. 
20140709, 00:04  #7 
Tribal Bullet
Oct 2004
3545_{10} Posts 
The AUTHORS file has one name. It's pretty good code, has unit tests and everything.
It's very interesting that integer factorization has a wealth of software but discrete logs in large prime characteristic have only this package and the heavy artillery written by the record holders. Stackoverflow has tons of factorization questions and trial division done badly in dozens of computer languages yet nobody cares about discrete logs. Yet there has to be tons of crypto that uses DiffieHellman over prime fields. In my weaker moments I have thought of building NFSDLP. Right now it's limited to just reading papers. 
20140709, 07:05  #8 
Jul 2014
13 Posts 
First, I want to thank you all for the replies.
Sorry I didn't provide more details about my problem. Some of the details were provided already in the replies: p  prime number q  odd prime divisor of (p1) g  generator t  target, 0 < t < p in Z\pZ p1Fact  array of divisors of (p1) x  unknown, 0 <= x < q  1 All arithmetic is done in modulo p. I know now that the answer should be x = 379721093484885118231722056, but I don't know how to find it using GDLOG. Also, I'm not sure yet what lc0Fact is and if I chose it correctly. From the README: Add factorization for lc(f0) ([p0 p1 p2 ...]) to configuration file (30 for example) This is how I chose lc0Fact (based on what I saw in example "30"): GDLOG modifies my configuration file and adds f0: [ 1488503186 321573326 3583848099 ] lc0Fact is an array of divisors of the last element of f0: 3583848099 I don't know why I have to add it manually. I attached my configuration file. Last fiddled with by xkyve on 20140709 at 07:24 
20140709, 08:09  #9 
Tribal Bullet
Oct 2004
DD9_{16} Posts 
My understanding is that just like NFS for factoring integers, NFS for discrete logs requires that you choose a polynomial pair to sieve over, composed of a rational and algebraic polynomial. Once you choose the leading coefficient of the algebraic polynomial, the other coefficients are determined automatically if you use the 'basem method'.
I would assume you could choose a different lc0 and GDLOG will change the other coefficients in lc[] to compensate. Another interesting aspect of NFSDLP is that there's a welldeveloped theory for selecting polynomials for integer factorization using NFS, and I think the same principles (find two polynomials whose values are simultaneously smooth) applies to NFSDLP, yet nobody uses the algorithms from integer factorization to choose good polynomials for discrete logs. Last fiddled with by jasonp on 20140709 at 08:14 
20140710, 07:02  #10 
Jul 2014
13 Posts 
I tried to run GDLOG on a different PC, thinking it was a problem with my hardware or ubuntu installation. I still can't obtain a solution. It outputs the same message all over again.
Any ideas? Last fiddled with by xkyve on 20140710 at 07:02 
20140710, 09:42  #11 
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·3·311 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help with discrete logarithm  pinnn  Information & Answers  43  20210318 15:40 
Discrete logarithm software  Unregistered  Information & Answers  39  20120427 20:08 
Finding totient using discrete logarithm  vector  Miscellaneous Math  3  20071120 18:50 
Solving discrete logarithm in 2 variables  Coffenator  Information & Answers  16  20071003 21:01 
Discrete logarithm mod Mersenne primes?  Unregistered  Information & Answers  0  20060827 15:32 