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



Скачать 84.41 Kb.
Дата30.04.2016
Размер84.41 Kb.
Алгоритм Евклида и его сложность.
Рассмотрим математические вопросы, связанные с шифрами, использующие операции с целыми числами. Обозначим 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. если и -чётные, то

НОДНОД();

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

НОДНОД();

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

НОДНОД().

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



. (6)

Пример 3.

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



(2)=4 (=3, =1).


База данных защищена авторским правом ©zodorov.ru 2016
обратиться к администрации

    Главная страница