mersenneforum.org GDLOG discrete logarithm usage example
 Register FAQ Search Today's Posts Mark Forums Read

2014-07-08, 13:55   #1
xkyve

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
Attached Files
 omega_dlog.txt (6.5 KB, 196 views)

2014-07-08, 20:57   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts

Quote:
 Originally Posted by xkyve 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
Huh? You say "709787689553880977598302546337 to the 7",

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.

2014-07-08, 21:11   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

2×5×839 Posts

Quote:
 Originally Posted by R.D. Silverman Also, WT is "q"????
floor(p/2) by my math.

 2014-07-08, 21:22 #4 jasonp Tribal Bullet     Oct 2004 5·709 Posts The GDLOG source is available here. I believe q above is the order of g mod p. Last fiddled with by jasonp on 2014-07-08 at 21:24
2014-07-08, 22:25   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

746410 Posts

Quote:
 Originally Posted by jasonp The GDLOG source is available here. I believe q above is the order of g mod p.
Thanks.

I checked the website. Do we know who wrote it?

 2014-07-08, 22:27 #6 fivemack (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.
 2014-07-09, 00:04 #7 jasonp Tribal Bullet     Oct 2004 354510 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 Diffie-Hellman over prime fields. In my weaker moments I have thought of building NFSDLP. Right now it's limited to just reading papers.
2014-07-09, 07:05   #8
xkyve

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 (p-1)
g - generator
t - target, 0 < t < p in Z\pZ
p1Fact - array of divisors of (p-1)

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.
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.
Attached Files
 config.txt (581 Bytes, 180 views)

Last fiddled with by xkyve on 2014-07-09 at 07:24

 2014-07-09, 08:09 #9 jasonp Tribal Bullet     Oct 2004 DD916 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 'base-m 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 well-developed 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 2014-07-09 at 08:14
 2014-07-10, 07:02 #10 xkyve   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 2014-07-10 at 07:02
2014-07-10, 09:42   #11
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts

Quote:
 Originally Posted by xkyve 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?
GIGO

 Similar Threads Thread Thread Starter Forum Replies Last Post pinnn Information & Answers 43 2021-03-18 15:40 Unregistered Information & Answers 39 2012-04-27 20:08 vector Miscellaneous Math 3 2007-11-20 18:50 Coffenator Information & Answers 16 2007-10-03 21:01 Unregistered Information & Answers 0 2006-08-27 15:32

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

Mon Aug 8 23:29:49 UTC 2022 up 32 days, 18:17, 1 user, load averages: 1.32, 1.42, 1.50