Нахождение обратного элемента по модулю через расширенный алгоритм Евклида - C#
Формулировка задачи:
Доброго времени суток. Возникла проблема с частью программы (где находится обратный элемент по модулю через расширенный алгоритм Евклида), вот код процедуры
Почему-то постоянно выдает неверное число (a*REM(a,b) != 1 (mod b) при проверке, число не нулевое), в чем ошибка?
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; }
Решение задачи: «Нахождение обратного элемента по модулю через расширенный алгоритм Евклида»
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; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д