C#. Длинная арифметика. Урок 9. Нахождение обратного

Длинная арифметика   22 марта 2013  Автор статьи:  

В данной статье мы научимся находить обратный элемент в кольце по модулю N. Для решения данной задачи воспользуемся расширенным алгоритмом Евклида. Итак, обычный алгоритм Евклида находит наибольший общий делитель двух чисел. Например: d = НОД(21, 28) = 7. Расширенный алгоритм Евклида, кроме того, что находит НОД решает уравнение ax+by=d=НОД(a,b). Для того, чтобы найти обратный элемент в кольце по модулю n достаточно решить уравнение ax+ny = d, при этом НОД(a, n) = 1, иначе решения не существует. Искомый x и будет обратным элементом. Рекурсивный алгоритм расширенного алгоритма Евклида достаточно известен и имеет компактный вид. Но в рамках данной статьи я бы хотел написать не рекурсивный расширенный алгоритм Евклида, который будет заниматься только поиском обратного. Как с помощью данного алгоритма найти обратный я описал выше, давайте поймем какие операции нам надо смоделировать. Основная идея рекурсивного алгоритма Евклида в том, что НОД(a,b) = НОД(b % a, a), очевидно, что данный переход должен происходить на каждом шаге нашего цикла. Кроме того нам нужно как — то подсчитываться НОД и x. Очевидно, что d на следующем шаге равняется x на предыдущем шаге минус q умножить на d на этом шаге, где q это b / a. Тогда x это d на предыдущем шаге.

public BigInteger Inverse(BigInteger n)
{
BigInteger a = new BigInteger(this.ToString());
BigInteger b = n, x = Zero, d = One;
while (a.CompareTo(Zero)==1)//a>0
{
BigInteger q = b.Div(a);
BigInteger y = a;
a = b.Mod(a);
b = y;
y = d;
d = x.Substract(q.Multiply(d));
x = y;
}
x = x.Mod(n);
if (x.CompareTo(Zero) == -1)//x<0 { x = (x.Add(n)).Mod(n); } return x; }

Конец алгоритма нормализует ответ, т.е., если обратный получился меньше нуля, то давайте сделаем его положительным.
Покроем наш метод тестами:

[TestMethod()]
public void modInverseTest()
{
BigInteger a = new BigInteger("22222222");
BigInteger n = new BigInteger("111111111");
Assert.AreEqual(BigInteger.One, a.Multiply(a.Inverse(n)).Mod(n));
a = new BigInteger("22");
n = new BigInteger("10000000000000001");
Assert.AreEqual(BigInteger.One, a.Multiply(a.Inverse(n)).Mod(n));
a = new BigInteger("139453498503948590345");
n = new BigInteger("11111111132432423424835039485750753494");
Assert.AreEqual(BigInteger.One, a.Multiply(a.Inverse(n)).Mod(n));
a = new BigInteger("222222220000000009876545678");
n = new BigInteger("1111111111111111111111111111111111171");
Assert.AreEqual(BigInteger.One, a.Multiply(a.Inverse(n)).Mod(n));
a = new BigInteger("2");
n = new BigInteger("11");
Assert.AreEqual(BigInteger.One, a.Multiply(a.Inverse(n)).Mod(n));
}

  • Cisa

    function Inverse(n){
    var a=n, b = n, x = 0, d = 1;
    while(a>0){
    var q = b/a, y = a;
    a = b%a;
    b = y;
    y = d;
    d = q*d;
    x = y;
    }
    x = x%n;
    if(x<0){
    x = (x+n)%n;
    }
    return x;
    }
    alert( Inverse(173) )

    В js ошибка есть, потому что все время выдает 1.

    Можно ли как то исправить?

    • a=n че за бред? а это то число от которого вы ищете обратное по модулю n.

Научиться программировать

  • на Delphi

  • на Java

  • на C++