Расширенный алгоритм Евклида

Один из важнейших результатов элементарной теории чисел утверждает, что наибольший общий делитель двух целых чисел выражается в виде их линейной комбинации с целыми коэффициентами. Пусть m и n - два целых числа, хотя бы одно из которых не равно нулю. Тогда их наибольший общий делитель d = НОД(m,n) выражается в виде

d = um+vn,

где u и v - некоторые целые числа. Результат этот очень важен для практики, т.к. позволяет вычислить обратный элемент к n в кольце вычетов по модулю m. Действительно, пусть числа m и n взаимно просты, т.е. НОД(m,n) = 1. Тогда

1 = um+vn,

откуда следует

vn = 1-um

1(mod m)

Нахождение обратного элемента в кольце вычетов Zm применяется во многих дискретных алгоритмах, например, в схеме кодирования с открытым ключом.

Для вычисления наибольшего общего делителя d и одновременно чисел u и v используется так называемый расширенный алгоритм Евклида. В обычном алгоритме Евклида пара чисел (a,b) в цикле заменяется на пару (b,r), где r - остаток от деления a на b, при этом наибольший общий делитель у обеих пар одинаковый. Начальные значения переменных a и b равны m и n соответственно. Алгоритм заканчивается, когда b становится равным нулю, при этом a будет содержать наибольший общий делитель.

Идея расширенного алгоритма Евклида заключается в том, что на любом шаге алгоритма хранятся коэффициенты, выражающие текущие числа a и b через исходные числа m и n. При замене пары (a,b) на пару (b,r) эти коэффициенты перевычисляются.

Итак, в алгоритме участвуют переменные a, b, u1, v1, u2, v2, для которых выполняется следующий инвариант цикла:

I(a, b, u1, v1, u2, v2): НОД(a,b) = НОД(m,n) a = u1m+v1n b = u2m+v2n

Начальные значения этих переменных обеспечивают выполнение инварианта:

a = m, b = n, u1 = 1, v1 = 0, u2 = 0, v2 = 1.

Условием завершения цикла, как и в обычном алгоритме Евклида, является равенство нулю переменной b:

Q(a, b, u1, v1, u2, v2): b = 0.

Осталось написать тело цикла, сохраняющее инвариант и уменьшающее абсолютную величину переменной b.

Это нетрудно сделать, исходя из инварианта цикла. В обычном алгоритме Евклида пара (a,b) заменяется на (b,r), где r - остаток от деления a на b.

a = gb+r, |r| < |b|.

Здесь g равняется целой части частного от деления a на b. Заметим, что в программировании, в отличие от школьной математики, операция взятия целой части перестановочна с операцией изменения знака:

целая часть(-x) = - целая часть(x)

Например, целая часть(-3.7) = -3. Это позволяет работать с отрицательными числами так же, как и с положительными, т.е. вообще не следить за знаком! Отметим также, что в большинстве языков программирования считается, что результат любой операции с целыми числами является целым числом, например, 8/3 = 2.

Переменная g вычисляется как целая часть частного от деления a на b:

g = целая часть (a/b)

Выразим остаток r в виде линейной комбинации a и b:

r = a-gb

Используя инвариант цикла, можно выразить r через исходные числа m и n:

r = a-gb = (u1m+v1n)-g(u2m+v2n) = = (u1-gu2)m+(v1-gv2)n.

Через u'1, v'1, u'2, v'2 обозначаются новые значения переменных u1, v1, u2, v2. При замене (a,b)