Даны x, y. Находит a, b, v: ax+by = d, где d=НОД(x, y)
Обратный элемент для x из Zn - такой a из Zn, что ax = 1(mod n)
Алгоритм Евклида.
Вычислим r - остаток от деления числа a на b, a = bq+r, 0 <= r < b.
Если r = 0, то b есть искомое число.
Если r =/= 0, то заменим пару чисел (a,b) парой (b,r) и перейдем к шагу 1.
int NOD(int a,int b) { while(a!=0 && b!=0) { if(a>=b) a=a%b; else b=b%a; } return a+b; // Одно - ноль }
При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.
Бинарный алгоритм Евклида.
Этот алгоритм использует соотношения для НОД:
НОД(2*a, 2*b) = 2*НОД(a,b) НОД(2*a, b) = НОД(a,b) при нечетном b,
Он иллюстрируется следующей программой:
m:= a; n:=b; d:=1; {НОД(a,b) = d * НОД(m,n)} while not ((m=0) or (n=0)) do begin if (m mod 2 = 0) and (n mod 2 = 0) then begin d:= d*2; m:= m div 2; n:= n div 2; end else if (m mod 2 = 0) and (n mod 2 = 1) then begin m:= m div 2; end else if (m mod 2 = 1) and (n mod 2 = 0) then begin n:= n div 2; end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin m:= m-n; end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin n:= n-m; end; end; {m=0 => ответ=d*n; n=0 => ответ=d*m}
Алгоритм решения уравнения ax+by = 1.
Определим матрицу E:
Вычислим r - остаток от деления числа a на b, a=bq+r, 0 <= r < b.
Если r=0, то второй столбец матрицы E даёт вектор ( x, y ) решений уравнения.
Если r =/= 0, то заменим матрицу E матрицей
Заменим пару чисел (a,b) на (b,r) и перейдем к шагу 2.
1 2
8 8 8
| |