Brandon Enright on Wed, 22 Jan 2020 00:57:08 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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


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

Furthermore, these p and q have been chosen so that p - 1 and q - 1
factor easily.  Also, gcd(p - 1, q - 1) = 2

Of course, eulerphi(n) = (p - 1) * (q - 1) and I know p and q even
though PARI can't factor n when it's big.

How could I go about computing the discrete log for g^x mod n = 12345?
(Actually, I don't care specifically about 12345 and I'd be happy with
pretty much any g and any result).

The trouble is, znstar(n) won't ever finish when p and q are large.
Since I know eulerphi(n) and also I've setup p - 1 and q - 1 to be
smooth, I figure there must be a way to construct the "bid structure"
anyways.

I must admit, I don't fully understand the details of the bid structure
or else it would probably be more obvious to me how to construct it by
hand using the knowledge about the factorization of n that I have.

Thanks in advance for any guidance!

Brandon