gdlog-support Mailing List for GDLOG

Hi,

Thanks for bug report.
There is a bug in the progs/gdlog.py:

 _GDLOG_SOLVE_EXEC = 'gdlg_dlog *-s %(seed)s* -if %(job)s.logbase -of
%(job)s.new.logbase %(job)s'

should be changed to

 _GDLOG_SOLVE_EXEC = 'gdlg_dlog *-s%(seed)s* -if %(job)s.logbase -of
%(job)s.new.logbase %(job)s'

After this change

Linear Sieve for Lattice (0, 1 - 2048) + (1 x + 0 y, 0 x + 1 y)  -2048 <= x
< 2048, 1 <= y < 2
t:7s y(q)=746  ny(nq)=745 sp0=3.57(p/s) sp1=0.03(p/y(q)) et=0.01h er=69 s=25
Sieve returned 25 relations, time 7s.
Ideals base 0: size: 5767 logs: 2242 prune threshold: 4325
Pruning...
After pruning ideals base 0: size: 2242
Ideals base 1: size: 5088 logs: 1911 prune threshold: 3816
Pruning...
After pruning ideals base 1: size: 1911
Logarithm of the 709787689553880977598302546337 to the unknown base is
175897608535665572229529683078
Saving number fields
Logarithm of the 709787689553880977598302546337 to the 7 is
379721093484885118231722056. Checking result: ok
Solve Time: 7 s



On Fri, Jul 4, 2014 at 11:05 AM, Gabi Pascalau <xk...@gm...> wrote:

> Hello,
>
> 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
> The answer should be x = 379721093484885118231722056
>
> 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
>
>
> ------------------------------------------------------------------------------
> Open source business process management suite built on Java and Eclipse
> Turn processes into business applications with Bonita BPM Community Edition
> Quickly connect people, data, and systems into organized workflows
> Winner of BOSSIE, CODIE, OW2 and Gartner awards
> http://p.sf.net/sfu/Bonitasoft
> _______________________________________________
> Gdlog-support mailing list
> Gdl...@li...
> https://lists.sourceforge.net/lists/listinfo/gdlog-support
>
>

Hello,

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
The answer should be x = 379721093484885118231722056

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

To find full solution you should find x mod q_i for all q_i | p - 1. In
this case

p - 1 =  2^3 * 3 *  79043 * 3998741 * 290240017*454197539

gdlog (and gnfs for dlog in general) is used to find x mod q for 'large' q,
for smaller q other methods should be used. This example is for
demonstration purpose only ---- p and q are too small. Using
http://pari.math.u-bordeaux.fr/ you can find that
x = 362274084216648467976382636880 in a matter of minutes without gdlog.

Oleg


On Tue, Jul 1, 2014 at 11:58 AM, Gabi Pascalau <xk...@gm...> wrote:

> Hello,
>
> Running GDLOG for example "30" gives me the following output (as expected):
> Logarithm of the 519335238006017621936447751736 to the 5 is 142363323.
>
> So x = 142363323 is the solution to the equation:
> g ^ (x * ((p - 1) / q)) mod p = t ^ ((p - 1) / q) mod p
> Am I correct so far?
>
> But I'm more interested in the solution to the following equation:
> g^x mod p = t mod p
> How can I find "x" in this case?
>
> Thank you
>
>
> ------------------------------------------------------------------------------
> Open source business process management suite built on Java and Eclipse
> Turn processes into business applications with Bonita BPM Community Edition
> Quickly connect people, data, and systems into organized workflows
> Winner of BOSSIE, CODIE, OW2 and Gartner awards
> http://p.sf.net/sfu/Bonitasoft
> _______________________________________________
> Gdlog-support mailing list
> Gdl...@li...
> https://lists.sourceforge.net/lists/listinfo/gdlog-support
>

Hello,

Running GDLOG for example "30" gives me the following output (as expected):
Logarithm of the 519335238006017621936447751736 to the 5 is 142363323.

So x = 142363323 is the solution to the equation:
g ^ (x * ((p - 1) / q)) mod p = t ^ ((p - 1) / q) mod p
Am I correct so far?

But I'm more interested in the solution to the following equation:
g^x mod p = t mod p
How can I find "x" in this case?

Thank you

Alpha version available:

http://sourceforge.net/projects/gdlog/files/