C＃ModInverse函数

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

Answer 1

由于.Net 4.0+使用特殊的模块化算术函数ModPow（生成“ X power Y modulo Z ”）来实现BigInteger，因此您不需要第三方库来模拟ModInverse。 如果n是素数，你需要做的就是计算：

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

有关更多详细信息，请查看Wikipedia： Modular multiplicative inverse ，section 使用Euler定理 ，特殊情况“当m是素数时” 。 顺便说一下，有一个更新的SO主题： 1 / BigInteger在c＃中 ，采用与CodesInChaos相同的方法。

Answer 2

 int modInverse(int a, int n) { int i = n, v = 0, d = 1; while (a>0) { int t = i/a, x = a; a = i % x; i = x; x = d; d = v - t*x; v = x; } v %= n; if (v<0) v = (v+n)%n; return v; } 

Answer 3

BouncyCastle Crypto库具有BigInteger实现，该实现具有大多数模块化算术function。 它位于Org.BouncyCastle.Math命名空间中。

Answer 4

 BigInteger modInverse(BigInteger a, BigInteger n) { BigInteger i = n, v = 0, d = 1; while (a > 0) { BigInteger t = i / a, x = a; a = i % x; i = x; x = d; d = v - t * x; v = x; } v %= n; if (v < 0) v = (v + n) % n; return v; } 

Answer 5

C＃没有内置任何内容来支持模运算。 您需要自己实现它，或者更好的是，找到一个库。

Answer 6

没有用于获取逆mod的库，但可以使用以下代码来获取它。

 // Given a and b->ax+by=d long[] u = { a, 1, 0 }; long[] v = { b, 0, 1 }; long[] w = { 0, 0, 0 }; long temp = 0; while (v[0] > 0) { double t = (u[0] / v[0]); for (int i = 0; i < 3; i++) { w[i] = u[i] - ((int)(Math.Floor(t)) * v[i]); u[i] = v[i]; v[i] = w[i]; } } // u[0] is gcd while u[1] gives x and u[2] gives y. // if u[1] gives the inverse mod value and if it is negative then the following gives the first positive value if (u[1] < 0) { while (u[1] < 0) { temp = u[1] + b; u[1] = temp; } }