С# ModInverse Function

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

Ответ 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 в С#, с тем же подходом предложенным CodesInChaos.

Ответ 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;
}

Ответ 3

BouncyCastle Библиотека Crypto имеет реализацию BigInteger, которая имеет большинство модульных арифметических функций. Он находится в пространстве имен Org.BouncyCastle.Math.

Ответ 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;
        }

Ответ 5

В С# нет встроенной модульной арифметики. Вам нужно реализовать его самостоятельно или, еще лучше, найти библиотеку.