Основы программирования



              

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


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

d = um+vn,

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

1 = um+vn,

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

vn = 1-um

vn
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.


Содержание  Назад  Вперед