c# - C# modPow 负指数技巧

Question

我尝试使用using System.Numerics.BigInteger;负指数并执行 modPow，我阅读了有关异常的文档，这就是为什么我做了一些技巧

//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 mod pCommon，其中 Φ(n) 是欧拉函数。