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

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

* Brandon Enright [2020-01-22 00:57]:
> Hi PARI folks,
> 
> I'm trying to compute discrete logarithms in carefully constructed
> fields.
> 
> I see the documentation for znlog() and znstar() and I've even gotten
> tests to work when the modulus of my field is a prime, p, (and p - 1 is
> smooth enough that it's easy to factor) because znprimroot() can find a
> primitive root easily.
> 
> The problem I have is when I try to compute things with a composite
> modulus.  Since most composites don't have a primitive root
> znprimroot() isn't an option and I think I need to use znstar() instead.
> 
> However, I don't see a way to tell znstar() about all the knowledge I
> have of the modulus.
> 
> Allow me to provide some numbers for a concrete example.  These numbers
> are much smaller than the ones I want to use but they should fit in an
> email:
> 
> p = 3039332125512668828764567700357785092292459210891950632595702374157691839749003 // prime
> q = 49812678250664513445348324781789367118153790741421464113188581126082567313365663 // prime
> n = p * q // this is my modulus

A few pointers:

1) as a rule, when working out in Z/NZ for composite N = \prod p^{e_p} with
known factorization, it's preferrable to use the Chinese remainders theorem,
solve mod p^{e_p} indepedently then use 'chinese'

2) you can tell the factoring machinery about known primes using 'addprimes'.
After addprimes([p,q]), znstar(p*q) [or eulerphi(p*q) for that matter]
will be very fast.

3) see ??5, all arithmetic functions support (integer) inputs in the
form of their factorization matrix, so a direct znstar([p,1;q,1]) will
be instantaneous as well.

Hope this helps !

Cheers,

    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]
`