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

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

Hello,

  your main problem is the definition of "discrete logarithm" in (Z/NZ)^*.
This group is in general not cyclic, i.e. it is not true that all elements
are of the form g^x for a *fixed* g. This is only true when N is a) 2 or an
odd prime power, or b) twice a number of the previous shape. In particular
your N = p*q is not of this shape and (Z/NZ)^* is not cyclic.

In this general situation, znstar returns 
* "independent" generators g_1, ..., g_r
* their orders d_1, ..., d_r  (satisfying the technical condition d_r | ... |
  d_1 that make the (d_i) unique; i.e., g_i^d_i = 1  [ and g_i^d != 1 for any
  0 < d < d_i ]

and any element x in (Z/NZ)^* can be written uniquely as 
  x = \prod_i {g_i}^{x_i}
for (unique) integers 0 <= x_i < d_i; znlog returns the (x_i)
[ discrete logarithm with respect to the (g_i) ].

In PARI-speak, with smaller parameters for readability:

? G = znstar(3 * 5, 1);  \\ N = 3*5 => non-cyclic, we will have r > 1
? G.gen  \\ the (g_i), r = 2 in this case
%2 = [7, 11]   \\ mod N implicitly
? G.cyc  \\ the (d_i)
%3 = [4, 2]
? znlog(8, G)  \\ 8 = g_1^3 * g_2^1
%4 = [3, 1]~
? factorback(Mod(G.gen, G.mod), %)  \\ quick check
%5 = Mod(8, 15)

Once we know the discrete logarithms of x and y wrt the g_i, it's easy to
compute the order of x and y, and check whether x = y^c for some 0 <= c < ord(y)
[ left as an exercise in this case, see ??matolvemod for a (very) general
solution ]

Cheers,

    K.B.

* Brandon Enright [2020-01-23 00:51]:
> -----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-----

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`