是否有内置函数可以让我计算(mod n)的模逆?例如19 ^ -1 = 11(mod 30),在这种情况下19 ^ -1 == -11 == 19;
由于.Net 4.0+使用特殊的模块化算术函数ModPow(生成“X
power Y
modulo Z
”)来实现BigInteger,因此您不需要第三方库来模拟ModInverse。如果n
是素数,你需要做的就是计算:
a_inverse = BigInteger.ModPow(a, n - 2, n)
有关更多详细信息,请查看维基百科:Modular multiplicative inverse,Using Euler's theorem部分,特殊情况“当m是素数时”。顺便说一句,有一个更近期的SO主题:1/BigInteger in c#,采用相同的方法suggested by CodesInChaos。
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;
}
BouncyCastle Crypto库具有BigInteger实现,该实现具有大多数模块化算术功能。它位于Org.BouncyCastle.Math命名空间中。
没有用于获取逆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;
}
}