Даны 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
| |
*
Обратная связь