Как вычислить обратный элемент по модулю c#

Question

Помогите, пожалуйста, реализовать алгоритм на c#, который находил бы обратный элемент по модулю при вводе числа и самого модуля. Обратным к числу a по модулю m называется такое число b, что: a*b=1(mod m) и его нередко обозначают через a^{-1}. Интересует алгоритм, который бы быстро работал с большими числами типа BigInteger. Нужно для реализации шифра. Нашла код (скорее всего python), работает хорошо, но не разобралась и не смогла переписать его на c# смотрела тут

def gcdex(a, b):
  if a == 0 :
    return b,0,1
  gcd,x,y = gcdex(b%a, a)
  return gcd, y - (b//a) * x, x #здесь целочисленное деление

def invmod(a, m):
  g, x, y = gcdex (a, m)
  return None if g > 1 else (x % m + m) % m

print(invmod(4,11)) #result 3   (4 * 3) % 11 = 1

Answer 1

Не понял суть задачи, для меня модуль числа - это его мантисса. То есть математический термин. Наверное имелся в виду остаток от деления?

Я не знаю, что за язык (наверное python), но попробую

static (int, int, int) gcdex(int a, int b)
{
    if (a == 0)
        return (b, 0, 1);
    (int gcd, int x, int y) = gcdex(b % a, a);
    return (gcd, y - (b / a) * x, x);
}

static int invmod(int a, int m)
{
    (int g, int x, int y) = gcdex(a, m);
    return g > 1 ? 0 : (x % m + m) % m;
}

static void Main(string[] args)
{
    Console.WriteLine(invmod(4, 11));
}

БЛОГ НА HUSL

Как вычислить обратный элемент по модулю c#

Ответы (1 шт):