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