Алгоритм Евклида вычисления НОД

Одним из способов вычисления НОД двух чисел является алгоритм Евклида, который описал его с своей книге «Нача­ла» около 300 лет до н.э. Полагают, что он не изобрел его, а сам алгоритм ешё старше лет на 200. Это древнейший нетривиальный алгоритм, который актуален и в наше время.

1. Вычислим r — остаток от деления числа а на b (а>b):

а = b q +r, 0£r< b.

2. Если r = 0, то b есть искомое число.

3. Если r ¹ 0, то заменим пару чисел (а, b) парой (b,r) и перейдем к шагу 1.

Остановка гарантируется, поскольку остатки от делений образуют строго убывающую последовательность.

Оценку сложности этого алгоритма дает следующая теорема.

Теорема. При вычислении наибольшего общего делителя НОД (а, b) с по­мощью алгоритма Евклида будет выполнено не более 5 р операций де­ления с остатком, где р есть количество цифр в десятичной записи меньшего из чисел а и b.

Вычисление обратных величин в кольце целых чисел

При вычислении ключей в асимметричных криптографических системах необходимо находить обратные элементы в кольце целых чисел Z _m. Элемент xÎ Z _m является обратным к аÎ Z _m, (x=а^-1), если

x · aº1 mod m или а^-1º x mod m.

В общем случае это сравнение может не иметь решений или иметь несколько решений. Оно имеет единственное решение тогда и только тогда, если числа а и m взаимно простые, то есть НОД (а, m) =1.

Рассмотрим основные способы нахождения обратных величин в Z_m.

1. Метод перебора. Проверить поочередно значения xÎ (1, 2,.... m -1), пока не выполнится сравнение x · аº1 mod m.

2. Если известна функция Эйлера (для RSA) j (m), то можно вычислить а^-1 mod m º а^{j ( m )-1}mod m, используя алгоритм быстрого возведения в степень. (Это следует из утверждения теоремы Эйлера: если а и m взаимно простые, то а ^φ(m) º1 mod m.)

3. Нахождение обратной величины а^-1 mod m с помощью расширенного алгоритма Евклида.

Алгоритм Евклида можно обобщить способом, который имеет большое практическое значение. При этом способе во время вычисле­ния НОД можно попутно вычислить такие целые числа x и y, что

а · x + b · y = НОД (а, b).

Этот вариант называется расширенным алгоритмом Евклида. Для вычисления обратной величины используется частный режим работы алгоритма Евклида, при котором

b= m и НОД (а, m)=1.

В самом деле сравнение x · аº1 mod m означает, что $ целое k, что верно:

а х + m k = 1mod m.

Эта задача равносильна поиску целых решенийуравнения

ах+ mk = 1.

Алгоритм поиска целых решений уравнения а х + m k = 1

Немного подправив алгоритм Евклида, можно достаточно быстро решать сравнения

ах + mk = 1mod m

при условии, что НОД(а, m)=1.

0. Определим матрицу Е =I -единичная матрица размером 2х2.

1. Вычислим r — остаток от деления числа а на m:

а = m q +r, 0£r< m.

2. Если r = 0, то второй столбец матрицы Е дает вектор [ x,k ]^T решений уравнения.

3. Если r¹0, то заменим матрицу Е матрицей

Е = Е • .

4. Заменим пару чисел (а, m) парой (m, r) и перейдем к шагу 1.

Три приведенных выше алгоритма относятся к разряду так назы­ваемых полиномиальных алгоритмов. Это название носят алгоритмы, сложность которых оценивается сверху степенным образом в зависи­мости от длины записи входящих чисел (см. подробности в [2]). Если наибольшее из чисел, подаваемых на вход алгоритма, не превос­ходит m, то сложность алгоритмов этого типа оценива­ется величиной O(ln ^c m), где с — некоторая абсолютная постоян­ная. Во всех приве­денных выше примерах с= 1.

Полиномиальные алгоритмы в теории чисел — большая редкость. Да и оценки сложности алгоритмов чаще всего опираются на какие-либо недоказанные, но правдоподобные гипотезы, обычно относя­щиеся к аналитической теории чисел.