C#ModInverse函数

Question

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

Answer 1

由于.Net 4.0+使用特殊的模块化算术函数ModPow(生成" Xpower Ymodulo 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 实现，它具有大多数模块化算术函数。它位于 Org.BouncyCastle.Math 命名空间中。