Intereting Posts
Установка формы Windows для самой нижней Как проверить, содержит ли тип конструктор без параметров? Издевательская структура в приложениях UWP Метод возврата задачи Stubbing в асинхронном модульном тесте Point-Cloud of Body с помощью Kinect SDK Как нажать на кнопку в datagrid после нахождения правильного имени пользователя в C # Как определить, является ли данная буква диска локальным, сопоставленным или USB-накопителем? Проблемы при создании модульного теста для ASP.NET MVC Как определить, будут ли windows спячки или приостановлены? Повторить политику в ITargetBlock Удаление десериализации Json с производными типами в Web-API Asp.Net Проверка орфографии приложений Windows Список просмотра списка WPF для SelectedItem и подпунктов Как правильно закрыть клиентский прокси (существующее соединение было принудительно закрыто удаленным хостом)? Получение имени / ключа JToken с помощью JSON.net

C # ModInverse Function

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

    Так как .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 .

     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.

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

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

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

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