### Problems with modular inversion

Posted:

**Sat Mar 26, 2016 3:51 am**First, thank you for this wonderful library. It's been a lifesaver.

I am using the ZZ class for a cryptography project. I am generating RSA keys, and using the Chinese Remainder Theorem RSASP1 primitive. One of the quantities needed is the modular inverse of the two primes, p and q : qInv = 1/q mod p; In the tests I'm running, 3 <= p <= 2^512 - 1 and 3 <= q <= 2^512 -1. When I call InvMod(q, p) I get a LogicError exception thrown about 50% of the time. It says that the first input is too large. I don't see that error mentioned in the documentation for the ZZ class. When I track it down in the code, it seems to be coming from an _ntl_gcompare operation when a >= n (q >= p) in g_lip_impl.h. Both q and p are of type ZZ.

I am not sure why this limitation exists. Both p and q are prime and greater than 0, so the inverse should exist. Am I missing something?

Thank you.

I am using the ZZ class for a cryptography project. I am generating RSA keys, and using the Chinese Remainder Theorem RSASP1 primitive. One of the quantities needed is the modular inverse of the two primes, p and q : qInv = 1/q mod p; In the tests I'm running, 3 <= p <= 2^512 - 1 and 3 <= q <= 2^512 -1. When I call InvMod(q, p) I get a LogicError exception thrown about 50% of the time. It says that the first input is too large. I don't see that error mentioned in the documentation for the ZZ class. When I track it down in the code, it seems to be coming from an _ntl_gcompare operation when a >= n (q >= p) in g_lip_impl.h. Both q and p are of type ZZ.

I am not sure why this limitation exists. Both p and q are prime and greater than 0, so the inverse should exist. Am I missing something?

Thank you.