C# ModInverse 函数 [英] C# ModInverse Function

问题描述

是否有内置函数可以让我计算 a(mod n) 的模逆?例如19^-1 = 11 (mod 30)，在这种情况下 19^-1 == -11==19;

Is there a built in function that would allow me to calculate the modular inverse of a(mod n)? e.g. 19^-1 = 11 (mod 30), in this case the 19^-1 == -11==19;

推荐答案

自从 .Net 4.0+ 使用特殊的模算术函数 ModPow 实现 BigInteger(产生X 幂 Y modulo Z")，您不需要第三方库来模拟 ModInverse.如果 n 是素数，你需要做的就是计算:

Since .Net 4.0+ implements BigInteger with a special modular arithmetics function ModPow (which produces "X power Y modulo Z"), you don't need a third-party library to emulate ModInverse. If n is a prime, all you need to do is to compute:

a_inverse = BigInteger.ModPow(a, n - 2, n)

有关更多详细信息，请查看维基百科:模乘逆，部分使用欧拉定理，特殊情况当 m 是质数时".顺便说一句，关于这个，有一个更新的 SO 主题:1/BigInteger in c#，采用 CodesInChaos 建议的相同方法.

For more details, look in Wikipedia: Modular multiplicative inverse, section Using Euler's theorem, the special case "when m is a prime". By the way, there is a more recent SO topic on this: 1/BigInteger in c#, with the same approach suggested by CodesInChaos.

这篇关于C# ModInverse 函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！