N – множество натуральных чисел, n множество натуральных чисел с 0, Z

Здесь r называется остатком. Существует несколько обозначений для остатков:

Простейшие свойства остатков.

1. так как

2. R(a + ib) = R(a), i Z,

так как a + ib = (q + i)b + r.

Если r = 0, то b делит a (обозначается b/a).

Из свойства 1 следует, что, если а делится на d, то а делится на –d. Поэтому среди всех общих делителей а и b существует наибольший натуральный делитель (обозначается НОД(а, b)). Если НОД(а, b) = 1, то а и b взаимно просты.

Лемма 1. Для любых а, b, i Z

НОД(а, b) = НОД(а+ ib, b).

Равенство в следующей лемме называется рекурсией Евклида.

НОД(n, n) = НОД(n-q n, n) = (R( n ), n).

Лемма доказана.

Следствие. Если НОД(n,n) = НОД(R(n),n) =
= НОД(R, R( n )= …=НОД(0, r),

то r = НОД(n, n). (2)

Данный способ нахождения НОД(n,n) называется алгоритмом Евклида.

Пример 1.

НОД(54,30) = НОД(24,30) = НОД(6,24) = НОД(0,6) = 6,

НОД(156,117) = НОД(39,117) = НОД(0,39) = 39.

В криптографии возможность применения любого алгоритма определяется сложностью этого алгоритма. Оценим сложность алгоритма Евклида. Будем считать за одну операцию одно деление в алгоритме Евклида. Отметим, что каждое равенство в (2) связано с одной операцией деления. Обозначим через m(d) минимальное число n> 0, для которого существует n, n> n>0 такое, что НОД(n, n) вычисляется при помощи (2) за d операций деления.

Легко вычислить m(d) для малых значений d.

m(1) = 2 (n = 2, n = 1);

m(2) = 3 (n = 3, n = 2);

m(3) = 5 (n = 5, n = 3).

Пусть n = m(d) и n - такое, что НОД(n, n) вычисляется за d шагов алгоритма Евклида (2). Обозначим n = q n + r, n = qr + r. Тогда для вычисления НОД(n, r) надо (d –1) операции в алгоритме Евклида, а для вычисления НОД(r, r) надо (d –2) операции в алгоритме Евклида. Из определения n следует

Вместе с тем, n m(d-1). Это следует из того, что для n существует r, позволяющее вычислять НОД(n, r) за (d –1) делений, а m(d-1) – наименьшее из натуральных чисел, обладающих этим свойством. Аналогично, для нахождения НОД(r, r) требуется (d –2) деления, а

Рассмотрим рекуррентное соотношение

При начальных условиях Ф(1) = 2, Ф(2) = 3. Тогда из неравенства (4) и равенства (5) и начальных значений Ф(1) = m(1), Ф(2) = m(2) следует, что

Суммируем по допустимым d.

Отсюда

= -1 - - .

Тогда из неравенства Ф(d) m(d) следует

Следовательно, для всех n

определяет верхнюю границу сложности алгоритма Евклида.

Существуют другие алгоритмы вычисления НОД. Алгоритм Стейна [Massey 94] основан на следующих равенствах:

1. 
   если и -чётные, то
   

2. 
   если -чётное, -нечётное, то
   

3. если и -нечётные, то

НОДНОД().

Сложность алгоритма Стейна. Пусть (s) – минимальное значение +, что s делений потребуется для нахождения НОД, Тогда

(1)=2 (=1, =1);