С # modPow отрицательный показатель трюк

Question

Я пытаюсь использовать using System.Numerics.BigInteger; и perfom modPow с отрицательным показателем, я прочитал документацию о Exception, поэтому я сделал некоторые трюк

//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); 

Но TMP 0. Как я могу решить, что проблема?

Answer 1

Ваш «трюк» только обманывает себя. BigInteger.Divide(BigInteger.One, a) почти всегда равен нулю, если a не равен 1. В любом случае это не так, как вычислять модульные инверсии. Необходимо реализовать расширенный алгоритм Евклида, или, если у вас есть полное разложение pCommon можно вычислить a^{Φ (pCommon) - 1} == a^-1 мод pCommon, где Φ (п) является euler totient function.