§ 2.6. Расширенный алгоритм Эвклида

У алгоритма Эвклида, описанного в предыдущем параграфе, есть еще один вариант, более мощный. Мощный в данном случае не означает более быстрый. Достоинство нового варианта в том, что наибольший общий делитель — лишь часть выходных данных. Пусть натуральные числа, их наибольший общий делитель. Расширенный алгоритм Эвклида подсчитывает не только но и два целых числа таких, что

Отметим, что (за исключением нескольких тривиальных случаев) если а оказывается положительным, то отрицательное, и наоборот.

Лучше всего вычислять эти числа, добавив некоторые инструкции в обычный алгоритм Эвклида так, чтобы подсчитывались одновременно. Именно поэтому новая процедура называется расширенным алгоритмом Эвклида. Приводимый здесь вариант этого алгоритма принадлежит Кнуту, автору знаменитой книги «Искусство программирования». Алгоритм описан во втором томе этого сочинения, см. [28] ([Д-4]).

Напомним, что алгоритм Эвклида состоит из последовательности делений с остатком. Наибольший общий множитель представляет собой последний ненулевой остаток в этой последовательности. Значит, нам надо найти способ записывать последний ненулевой остаток в виде (6.1).

Суть алгоритма Кнута в том, что нам не следует ждать, пока мы дойдем до последнего ненулевого остатка; вместо этого нам стоит записывать в таком виде каждый из получающихся остатков. Такие действия должны приводить, по-видимому, к большому количеству дополнительной работы. Как мы увидим позднее, это не совсем так.

Предположим, что для вычисления наибольшего общего делителя чисел мы выполнили последовательность делений (5.1). Перепишем ее, сопровождая каждую операцию записью предполагаемого представления остатка:

Числа мы и хотим определить. Необходимую информацию удобно свести в таблицу:

(см. скан)

Отметим прежде всего, что таблица начинается с двух строчек, которым в ней не следовало бы быть. Действительно,

стоящие в первом столбце этих строк числа не являются остатками в каких-либо операциях деления. Мы даем этим строчкам номера —1 и 0, подчеркивая тем самым их «незаконность». Вскоре мы обоснуем их необходимость.

Что же мы хотим сделать? Мы хотим заполнить столбцы Предположим на минуту, что мы получили таблицу заполненной до некоторой, скажем до строки. Для заполнения строки необходимо прежде всего разделить на . В результате получатся первые два элемента строки. Не будем забывать, что Таким образом,

Из строчек мы можем взять значения Можно записать

Подставляя эти значения в (6.3), получаем

Поэтому

Заметим, что для вычисления нам понадобились только частное и данные из двух строк таблицы, непосредственно предшествующих Вот почему алгоритм Кнута такой эффективный. Для заполнения очередной строки достаточно знать две строчки, непосредственно предшествующие ей; все остальные строчки хранить не обязательно.

Итак, мы получили рекуррентную процедуру. Все, что необходимо — это научиться ее запускать. Именно для этого мы

и добавили в таблицу две «незаконные» строки. Найти в них значения очень просто. Придавая им тот же смысл, что и в остальных строках, мы должны получить

Поэтому можно просто положить

и процедуру можно запускать.

В результате цепочки делений с остатком мы получим равенство и вычислим такие целые числа что

Значит Заметим, что, зная мы можем найти по формуле

Поэтому достаточно вычислять только первые три столбца таблицы.

Приведем численный пример. Если то (полная) таблица выглядит так:

(см. скан)

Поэтому и

Пришло время разобраться, почему алгоритм дает правильный ответ и почему он завершает свою работу. Как и подразумевается названием, расширенный алгоритм Эвкли-да представляет собой просто алгоритм Эвклида из предыдущего параграфа, дополненный инструкциями для вычисления значений Поэтому он останавливается, и наибольший общий делитель составляет часть выходных данных. Кроме того, в каждой строке числа из столбцов а; и у удовлетворяют равенству типа (6.1), в котором число заменено остатком из соответствующей строки. В частности, равенство (6.1) выполняется, если в качестве а и 0 взять числа из столбцов строки, отвечающей последнему ненулевому остатку. Расширенный алгоритм Эвклида приводит к следующей теореме.

Теорема. Пусть наибольший общий делитель натуральных чисел Тогда существуют такие целые числа что

Заметим, что пара чисел упомянутая в теореме, не единственная. На самом деле таких пар бесконечно много. Например, возьмем для которых и рассмотрим какое-нибудь целое к. Тогда, как несложно проверить,

Приложив столько усилий к вычислению разумно задаться вопросом, для чего эти числа могут понадобиться. Проще всего добраться до ответа, продолжая читать эту книгу. Знание этих чисел необходимо для получения большого числа принципиально важных результатов, включая выбор ключей в системе шифрования RSA.

Упражнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)