C# modPow negative exponent trick

Question

I try to use using System.Numerics.BigInteger; and perfom modPow with negative exponent, I read documentation about Exception, that's why I did some trick

//a^(-x) mod n == (a^(-1))^x mod n
BigInteger tmp = BigInteger.ModPow(BigInteger.Divide(BigInteger.One, a), 
                 secretKey, pCommon);
BigInteger resBigInteger = BigInteger.Multiply(b, tmp); 

But tmp is 0. How I can resolve that problem?

Answer 1

Your "trick" is only fooling yourself. BigInteger.Divide(BigInteger.One, a) is almost always zero unless a is 1. In any event, this is not how to compute modular inverses. You must implement the Extended Euclidean algorithm, or, if you have the complete factorization of pCommon you can compute a^{Φ(pCommon) - 1} == a^-1 mod pCommon, where Φ(n) is the euler totient function.