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

[Brandon Enright <bmenrigh@brandonenright.net>]

Hi Karim, thank you very much for your response! I will respond inline.


On Wed, 22 Jan 2020 02:19:31 +0100
Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

> > 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'

The document I'm reading actually mentioned using Chinese Remainder
Theorem but I didn't understand the details.  I was able to compute the
znlog() for p-1 and q-1 but when I tried to put them together I got:

  *** chinese: inconsistent chinese t_INTMOD , t_INTMOD.

I thought this was because p-1 and q-1 both share 2 as a prime factor.

For what it's worth, I'm reading
https://toadstyle.org/cryptopals/61.txt, specifically the section on
RSA and trying to implement the very last comment about chosen
ciphertext/plaintext in that note.


> 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.

This is great! I had no idea about this feature.  This is exactly the
feature I needed to tell other features about the factorization.

> 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.

This is a very nice feature.  Had I known this I wouldn't have needed
to know about addprimes().  Either is exactly what I need.


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?

I'm assuming that this result is telling me some x^y mod n = 5 but I'm
not sure what x was used, and if that -63127...42 number is y or
something else?

Obviously I'm in a bit of my head with all of this.  I don't really
know much number theory so much of the documentation leaves me confused
and unsure of what it all means.

Thank you for your patience and guidance walking an amateur through
these things :-)

Brandon