Нахождение обратного элемента по модулю через расширенный алгоритм Евклида - C#

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток. Возникла проблема с частью программы (где находится обратный элемент по модулю через расширенный алгоритм Евклида), вот код процедуры
double REM(double a, double b)
        {
            double r1 = 1; double r2 = 1; double t1 = 1; double t2 = 1; int k = 0;
            do
            {
                k++;
                if (k == 1)
                {
                    r1 = Math.Ceiling(-((b / a) % b)); t1 = b % a;
                }
                else if (k == 2)
                {
                    r2 = (Math.Ceiling((1 - r1 * a / t1))-1) % b; t2 = a % t1;
                }
                else if (k % 2 == 1)
                {
                    r1 = Math.Ceiling((r1 - r2 * t1 / t2) % b); t1 = t1 % t2;
                }
                else if (k % 2 == 0)
                {
                    r2 = (Math.Ceiling((r2 - r1 * t2 / t1))-1) % b; t2 = t2 % t1;
                }
            }
            while ((t1 != 0) && (t2 != 0));
            if (k % 2 == 0) if (t1 != 1) return 0; else return r2;
            else if (t2 != 1) return 0; else return r1;
        }
Почему-то постоянно выдает неверное число (a*REM(a,b) != 1 (mod b) при проверке, число не нулевое), в чем ошибка?

Решение задачи: «Нахождение обратного элемента по модулю через расширенный алгоритм Евклида»

textual
Листинг программы
private double BinModPow(double a, double b, double n)
        {
            decimal x = (decimal)b;
            int i = 0;
            do
            {
                if (x % 2 == 1) x--;
                x = x / 2;
                i++;
            }
            while (x > 0);
            x = (decimal)b;
            decimal[] ar = new decimal[i];
            for (i = 0; i < ar.Length; i++)
            {
                ar[i] = x % 2;
                if (x % 2 == 1) x--;
                x = x / 2;
            }
            x = (decimal)a;
            for (i = ar.Length-2; i >= 0; i--)
            {
                x = (x * x) % (decimal)n;
                x = (x * (decimal)Math.Pow(a, (double)ar[i])) % (decimal)n;
            }
            return (double)x;
        }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

12   голосов , оценка 3.917 из 5
Похожие ответы