C # ModInverse Функция

Question

Есть ли встроенная функция, которая позволила бы мне вычислить модульную инверсию a (mod n)? например 19 ^ -1 = 11 (мод 30), в этом случае 19 ^ -1 == -11 == 19;

Answer 1

Так как .Net 4.0+ реализует BigInteger со специальной модульной арифметической функцией ModPow (которая производит «X power Y modulo Z»), вам не нужна сторонняя библиотека для эмуляции ModInverse. Если n простое число, все, что вам нужно сделать, это вычислить:

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

Для получения более подробной информации, смотрите в Википедии: Модульный мультипликативный обратный , сечение Используя теорему Эйлера , особый случай «когда 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 имеет реализацию BigInteger, которая имеет большинство модульных арифметических функций.Он находится в пространстве имен Org.BouncyCastle.Math.

Answer 4

Нет библиотеки для получения обратного мода, но для ее получения можно использовать следующий код:

// 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;
        }
}