Problem in BigInteger::inverseModulo


#1

Hello Jucers,

I noticed the following test in BigInteger::inverseModulus

    if (! (*this)[0])
    {
        // not invertible
        clear();
        return;
    }

Hence, if the number is even, the inverse is deemed to not exist and the operation is aborted. This is reasonable when the modulus is a power of 2, but it is not correct in general. An inverse exists if the number is coprime with the modulus, so the test should be:

    if (findGreatestCommonDivisor(modulus) != 1)
    {
        // not invertible
        clear();
        return;
    }

This issue is found in the latest code from github.

Cheers,

Bill


#2

Thanks Bill, I’ll sanity-check that!