Реферат: Применение алгоритма RSA для шифрования потоков данных

Если , то заменим пару чисел парой и перейдем к
шагу 1.

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

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

.

Пусть также , , , , - последователь­ность Фибоначчи. Индукцией по от до легко доказывается неравенство . А так как , то имеем неравенства и .

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

2.2.3. Алгоритм решения уравнения

0) Определим матрицу .

1) Вычислим - остаток от деления числа на , , .

2. Если , то второй столбец матрицы даёт вектор
   решений уравнения.

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

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

Если обозначить через матрицу , возникающую в процессе рабо­ты алгоритма перед шагом 2 после делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство . Поскольку числа и взаимно просты, имеем , и это доказы­вает, что алгоритм действительно даёт решение уравнения . Буквой мы обозначили количество делений с остатком, которое в точ­ности такое же, как и в алгоритме Евклида.

Три приведённых выше алгоритма относятся к разряду так называе­мых полиномиальных алгоритмов. Это название носят алгоритмы, слож­ность которых оценивается сверху степенным образом в зависимости от длины записи входящих чисел. Если наибольшее из чисел, подаваемых на вход алгоритма, не превосходит , то сложность алгоритмов этого типа оценивается величиной , где - некото­рая абсолютная постоянная. Во всех приведённых выше примерах .

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

Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях все же можно предложить последовательность действий, которая, «если повезет», быстро приводит к требуемому ре­зультату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную опен­ку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение ра­боты. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших опенок сложности.

Мы будем иногда использовать слова детерминированный алгоритм, чтобы отличать алгоритмы в обычном смысле от вероятностных алго­ритмов.

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

. (8)

Например, речь может идти о решении квадратичных сравнений, если степень многочлена равна 2. Другими словами, мы должны отыскать в поле все элементы, удовлетворяющие уравнению .

Согласно малой теореме Ферма, все элементы поля являются од­нократными корнями многочлена . Поэтому, вычислив наибольший общий делитель , мы найдем многочлен , множест­во корней которого в поле совпадает с множеством корней многочлена , причем все эти корни однократны. Если окажется, что многочлен имеет нулевую степень, т. е. лежит в поле , это будет означать, что сравнение (8) не имеет решений.

Для вычисления многочлена удобно сначала вычислить многочлен ,