Re: Computing discrete logs mod N when I know phi(N)?

[Brandon Enright <bmenrigh@brandonenright.net>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Alright I figured out more details which I will describe below:

On Wed, 22 Jan 2020 07:10:55 +0000
Brandon Enright <bmenrigh@brandonenright.net> wrote:

> > > p =
> > > 3039332125512668828764567700357785092292459210891950632595702374157691839749003
> > > // prime q =
> > > 49812678250664513445348324781789367118153790741421464113188581126082567313365663
> > > // prime n = p * q // this is my modulus    
> > 
>
> Unfortunately I'm a bit stuck using my example above.  First I init
> the group with znstar():
> 
> g = znstar(n, 1);
> 
> Then when I use znlog instead of getting one number back, I'm getting
> 2 in a column vector.  For example with the log of 5:
> 
> znlog(5, g)
> =
> [-63127347047617664945936273330073227063449799858664932302178759330922764129399588617443353900120252459589049390676980990590388726960654101199547861106561968542,
> -1]~
> 
> The log of other numbers tend to produce two large numbers, it just so
> happens that 5 produces -1 for the second number.
> 
> I don't know how to interpret these results.  What is the generator
> point / base / root of the log?


Okay I figured out that the bid structure I get out of znstar() has an
element '.gen' which is the generator.

As best I can tell, this is the point that is the base of the log.

So taking the discrete log of 127 via znlog:

GP/PARI> l = znlog(127, g)
%47 =
[16315058403787806876247495072223306909217287931523476034034216154860222224253448025436446749004031827935610293025623864473472712324783463821983523799767820455,
- -27666885693580666438437181700991665481474826242004716935879091550742082595641581]~

And when I raise g.gen to the first number in that column vector
163150584[...]7820455 I get -127.

GP/PARI> n - lift(modexp(g.gen[1], l[1], n))
%48 = 127

I'm not sure why I get -127 instead of 127.  That's why I'm doing n -
the result.

When I try the log of 128 instead I get 128 out directly:

GP/PARI> l = znlog(128, g);
GP/PARI> lift(modexp(g.gen[1], l[1], n))
%53 = 128

This is certainly progress!

I still don't understand why znlog() is giving me two results back.  I
also don't understand why sometimes the result is negative.

Thanks again for the help and patience while I work though these
details!

Brandon

-----BEGIN PGP SIGNATURE-----

iF0EARECAB0WIQQsPI0+tjl0LJJzd/apoY/MCyX3ggUCXijf4AAKCRCpoY/MCyX3
giHTAKCmEuTUEkZ3WVfkHzTE/gONUwsJ9gCfXdZsnQeSp9no7xVpsyfVSgRHqYM=
=MS1E
-----END PGP SIGNATURE-----