mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Closed Thread
 
Thread Tools
Old 2014-07-08, 13:55   #1
xkyve
 
Jul 2014

13 Posts
Arrow 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
File Type: txt omega_dlog.txt (6.5 KB, 196 views)
xkyve is offline  
Old 2014-07-08, 20:57   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts
Default

Quote:
Originally Posted by xkyve View Post
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.
R.D. Silverman is offline  
Old 2014-07-08, 21:11   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

2×5×839 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Also, WT<blank> is "q"????
floor(p/2) by my math.
science_man_88 is online now  
Old 2014-07-08, 21:22   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

5·709 Posts
Default

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
jasonp is offline  
Old 2014-07-08, 22:25   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

746410 Posts
Default

Quote:
Originally Posted by jasonp View Post
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?
R.D. Silverman is offline  
Old 2014-07-08, 22:27   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

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.
fivemack is offline  
Old 2014-07-09, 00:04   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

354510 Posts
Default

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.
jasonp is offline  
Old 2014-07-09, 07:05   #8
xkyve
 
Jul 2014

13 Posts
Default

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

Last fiddled with by xkyve on 2014-07-09 at 07:24
xkyve is offline  
Old 2014-07-09, 08:09   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DD916 Posts
Default

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
jasonp is offline  
Old 2014-07-10, 07:02   #10
xkyve
 
Jul 2014

13 Posts
Default

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
xkyve is offline  
Old 2014-07-10, 09:42   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts
Default

Quote:
Originally Posted by xkyve View Post
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
R.D. Silverman is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help with discrete logarithm pinnn Information & Answers 43 2021-03-18 15:40
Discrete logarithm software Unregistered Information & Answers 39 2012-04-27 20:08
Finding totient using discrete logarithm vector Miscellaneous Math 3 2007-11-20 18:50
Solving discrete logarithm in 2 variables Coffenator Information & Answers 16 2007-10-03 21:01
Discrete logarithm mod Mersenne primes? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔