Solving a discrete logarithm using GDlog

I am trying to calculate an $x$, such that $t = g^x \pmod p$ in order to crack a weak ElGamal encryption for university.

I found GDlog, but I cant figure out how I can use the input to calculate my $x$.

Here is what we got (from gdlogs example code):

p:1000000000000000000000000000057 //prime number, modulus
q:290240017                       //(p-1)/2
g:5                               //generator
t:519335238006017621936447751736  //member of the group


GDlogs result: Logarithm of the 519335238006017621936447751736 to the 5 is 142363323. My question is: What is the number that GDlog outputs (142363323)?

This is what is written in the README:

Find $0 \le x < q - 1$ such that $g^{x (p-1)/q} \pmod p = b^{(p-1)/q} \pmod p$ (assuming that such $x$ exists).

But I still can't figure out how to do it.

• I don't understand the following relation: 362274084216648467976382636880 = 142363323 mod (p-1)/q Can someone please elaborate how to get 362274084216648467976382636880 from 142363323?
– user15129
Commented Jun 25, 2014 at 12:24

1 Answer

$((g \mod p)^{(p-1)/q})^{142363323} = (t \mod p)^{(p-1)/q}$

Equivalently,

$(g \mod p)^{362274084216648467976382636880} = (t \mod p)$

That is,

$362274084216648467976382636880 = 142363323 \mod \frac {p-1}q$

• Thank you very much, that answered my question. Is there a way to mark this as the answer? Commented May 8, 2013 at 9:35
• @benmuell Click the checkbox left of the answer (and upvote it :-)) Commented May 8, 2013 at 12:54
• How to get 362274084216648467976382636880 from 142363323 then? Commented Apr 30, 2014 at 23:10