ДИПЛОМНАЯ РАБОТА на тему Применение алгоритма RSA при шифровании. Применение алгоритма rsa при шифровании потоков данных
 Скачать 1.17 Mb.
|
 ,легко доказываемого индукцией по  .Так как каждое вычисление на шаге 2 требует не более трёх умножений по модулю  и этот шаг выполняется  раз, то сложность алгоритма может быть оценена величиной  .Второй алгоритм - это классический алгоритм Евклида вычисления наибольшего общего делителя целых чисел. Мы предполагаем заданными два натуральных числа  и  и вычисляем их наибольший общий делитель  .2.2.2. Алгоритм Евклида Вычислим  - остаток от деления числа на ,  ,  .Если  , то есть искомое число.Если  , то заменим пару чисел  парой  и перейдем кшагу 1. Теорема 1. При вычислении наибольшего общего делителя с помощью алгоритма Евклида будет выполнено не более  операций деления с остатком, где  есть количество цифр в десятичной записи меньшего из чисел и .Доказательство. Положим  и определим  - последовательность делителей, появляющихся в процессе выполнения шага 1 алгоритма Евклида. Тогда .Пусть также  ,  ,  ,  , - последовательность Фибоначчи. Индукцией по от  до  легко доказывается неравенство  . А так как  , то имеем неравенства  и  .Немного подправив алгоритм Евклида, можно достаточно быстро решать сравнения  при условии, что  . Эта задача равносильна поиску целых решений уравнения  .2.2.3. Алгоритм решения уравнения 0) Определим матрицу  .1) Вычислим - остаток от деления числа на , , .Если , то второй столбец матрицы  даёт вектор  решений уравнения. Если , то заменим матрицу матрицей  .Заменим пару чисел парой и перейдем к шагу 1.Если обозначить через  матрицу , возникающую в процессе работы алгоритма перед шагом 2 после  делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство  . Поскольку числа и взаимно просты, имеем  , и это доказывает, что алгоритм действительно даёт решение уравнения . Буквой  мы обозначили количество делений с остатком, которое в точности такое же, как и в алгоритме Евклида.Три приведённых выше алгоритма относятся к разряду так называемых полиномиальных алгоритмов. Это название носят алгоритмы, сложность которых оценивается сверху степенным образом в зависимости от длины записи входящих чисел. Если наибольшее из чисел, подаваемых на вход алгоритма, не превосходит , то сложность алгоритмов этого типа оценивается величиной  , где  - некоторая абсолютная постоянная. Во всех приведённых выше примерах  .Полиномиальные алгоритмы в теории чисел - большая редкость. Да и опенки сложности алгоритмов чаше всего опираются на какие-либо не доказанные, но правдоподобные гипотезы, обычно относящиеся к аналитической теории чисел. Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях все же можно предложить последовательность действий, которая, «если повезет», быстро приводит к требуемому результату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную опенку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение работы. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших опенок сложности. Мы будем иногда использовать слова детерминированный алгоритм, чтобы отличать алгоритмы в обычном смысле от вероятностных алгоритмов. Как пример, рассмотрим вероятностный алгоритм, позволяющий эффективно находить решения полиномиальных сравнений по простому модулю. Пусть — простое число, которое предполагается большим, и  - многочлен, степень которого предполагается ограниченной. Задача состоит в отыскании решений сравнения . (8)Например, речь может идти о решении квадратичных сравнений, если степень многочлена  равна 2. Другими словами, мы должны отыскать в поле  все элементы, удовлетворяющие уравнению  .Согласно малой теореме Ферма, все элементы поля  являются однократными корнями многочлена  . Поэтому, вычислив наибольший общий делитель  , мы найдем многочлен  , множество корней которого в поле совпадает с множеством корней многочлена , причем все эти корни однократны. Если окажется, что многочлен имеет нулевую степень, т. е. лежит в поле , это будет означать, что сравнение (8) не имеет решений.Для вычисления многочлена удобно сначала вычислить многочлен  , пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число предполагается большим). А затем с помощью аналога алгоритма Евклида вычислить  . Всё это выполняется за полиномиальное количество арифметических операций.Таким образом, обсуждая далее задачу нахождения решений сравнения (8), мы можем предполагать, что в кольце многочленов  справедливо равенство 2.2.4. Алгоритм нахождения делителей многочлена в кольце 1) Выберем каким-либо способом элемент  .Вычислим наибольший общий делитель  .Если многочлен  окажется собственным делителем , то многочлен распадётся на два множителя и с каждым из них независимо нужно будет проделать все операции, предписываемые настоящим алгоритмом для многочлена .4) Если окажется, что  или  , следует перейти к шагу 1 и. выбрав новое значение  , продолжить выполнение алгоритма.Количество операций на шаге 2 оценивается величиной  , если вычисления проводить так, как это указывалось выше при нахождении . Выясним теперь, сколь долго придётся выбирать числа , пока на шаге 2 не будет найден собственный делитель .Количество решений уравнения  в поле не превосходит  . Это означает, что подмножество  элементов , удовлетворяющих условиям  ,состоит не менее, чем из  элементов. Учитывая теперь, что каждый ненулевой элемент  удовлетворяет одному из равенств  , либо  , заключаем, что для  одно из чисел  будет корнем многочлена  , а другое - нет. Для таких элементов многочлен |