# 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 Jun 25 '14 at 12:24

$((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? – benmuell May 8 '13 at 9:35
@benmuell Click the checkbox left of the answer (and upvote it :-)) – Thomas May 8 '13 at 12:54
How to get 362274084216648467976382636880 from 142363323 then? – Smit Johnth Apr 30 '14 at 23:10