Алгоритм Евклида и его сложность.

Рассмотрим математические вопросы, связанные с шифрами, использующие операции с целыми числами. Обозначим N – множество натуральных чисел,  N - множество натуральных чисел с 0, Z –множество целых чисел. Если  a,b  Z, b 0, то по теореме Евклида существует единственная пара целых чисел q, r таких, что 
a = bq + r, 0  r < .                                                                                (1)
Здесь r называется остатком. Существует несколько обозначений для остатков:
 r = R(a), r = a(mod b)  и другие.
Простейшие свойства остатков.
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).
Д о к а з а т е л ь с т в о. Если d/a, d/b, то a = Qd, b = Qd. Тогда 
a  + ib = d( Q+ iQ),  то есть d/(a + ib). Значит НОД(а, b)  НОД(а+ ib, b). Аналогично, пусть d/(a + ib) и d/b, то есть a + ib = Qd, b = Qd. Тогда 
a = d( Q- iQ), то есть d/a. Это значит, что НОД(а, b)  НОД(а+ ib, b). Из полученных неравенств следует, что НОД(а, b) = НОД(а+ ib, b). Лемма доказана.
Равенство в следующей лемме называется рекурсией Евклида.
Лемма 2.  Для любых  n,  n Z, n0,
 . 
Д о к а з а т е л ь с т в о. Так как n = nq +R( n ), то по лемме 1:
НОД(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 следует
m(d) =  q n + r.                                                                                       (3)
Вместе с тем, n m(d-1). Это следует из того, что для n существует r, позволяющее вычислять НОД(n, r) за (d –1) делений, а m(d-1) – наименьшее из натуральных чисел, обладающих этим свойством. Аналогично, для нахождения НОД(r, r) требуется  (d –2) деления, а    
m(d-2) – наименьшее из таких чисел. Тогда  r  m(d-2). Из этих оценок и (3) следует, что
m(d)  m(d-1) + m(d-2).                                                                               (4)         
Рассмотрим рекуррентное соотношение
Ф(d) = Ф (d-1) + Ф (d-2).                                                                            (5)         
При начальных условиях Ф(1) = 2, Ф(2) = 3. Тогда из неравенства (4) и равенства (5) и начальных значений Ф(1) = m(1), Ф(2) = m(2)  следует, что 
Ф(d)  m(d) для всех d  1. Рекуррентное соотношение (5) определяет числа Фибоначчи (1202 г.). Найдем эти числа методом производящих функций. Пусть  Ф(d) x = Ф(x) – формальный ряд.  Для d  3
Ф(d) x = xФ(d-1)x+ xФ(d-2)x. 
Суммируем по допустимым d.
Ф(d) x = xФ(d-1)x+ xФ(d-2)x. 
Отсюда
Ф(x) – 3x-2x = x(Ф(x) – 2x) + x Ф(x).
Ф(x)(1  - x - x) =  x+ 2x.
Ф(x) = = -1 -  = -1 - = 
= -1 -  - .
.
Отсюда
.
Тогда из неравенства Ф(d)  m(d) следует
d  1,44 log m(d).
Следовательно, для всех n
                                                                                    
определяет верхнюю границу сложности алгоритма Евклида.
Пример 2. 

Существуют другие алгоритмы вычисления НОД. Алгоритм Стейна [Massey 94] основан на следующих равенствах:
1.	если  и -чётные, то
НОДНОД();
2.	если -чётное, -нечётное, то
НОДНОД();
3. если   и -нечётные, то
НОДНОД().
Сложность алгоритма Стейна. Пусть (s) – минимальное значение +, что s делений потребуется для нахождения НОД,  Тогда
.                                                                                             (6)
Пример 3. 
(1)=2                   (=1, =1);
(2)=4                   (=3, =1).