Karim Belabas on Wed, 22 Jan 2020 02:19:31 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Computing discrete logs mod N when I know phi(N)? |
* 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] `