BIG.modinv works only for prime modules

[ManudL2000]

Looking at the method "modinv" in the file zen_big.c, seems that this method find succesfully the inverse of a big number only if the modulo is a prime number.
When the modulo is a composite number two things can happen:

1. the computation doesn't stop (for example when the big number in input is not invertible).
2. It gives a wrong inverse.

For example in the ring Z/6Z the element 5 is invertible and its inverse is 5 since 25 mod 6 = 1. Instead the output of the function is 3.

local x = BIG.new(5)
local module = BIG.new(6)
local inv_x = x:modinv(module)
print(inv_x:decimal())

[matteo-cristino]

Looking deeper into milagro library it seems to use the binary method in order to compute the modulo inverse. This algorithm, if I remember well, works only with odd modulos. Need to search better for this, if this is the case than we should add a check on the parity of the modulo.

[jaromil]

I agree adding checks is the right approach, let's introduce a parity check?
Also the modinv function could check for 2^BIGBITS values and switch to use the BIG_XXX_invmod2m function in milagro which is much faster. See src/big.c.in at line 1432

/* a=1/a mod 2^BIGBITS. This is very fast! */
void BIG_XXX_invmod2m(BIG_XXX a)

and

/* Set r=1/a mod p. Binary method */
/* SU= 240 */
void BIG_XXX_invmodp(BIG_XXX r,BIG_XXX a,BIG_XXX p)

the latter has internal checks on parity, but I don't know this technique well enough to judge on its constraints. I know that a must be <p on entry.