Применение алгоритма RSA для шифрования потоков данных — страница 14
случайного выбора и последующей проверки (15). Докажем, что из выполнимости (14-15) следует, что каждый делитель числа удовлетворяет одному из сравнений или (16) Не уменьшая общности, можно считать, что - простое число. Введем теперь обозначения и - нечётные числа. Из (15) и сравнения следует, что означающие (в силу того, что символ Якоби может равняться лишь -1 или +1), что При это равенство означает, что при и Информация такого рода получается и в случае произвольных простых чисел и с указанными выше свойствами. Опишем схему алгоритма Адлемана - Ленстры для проверки простоты 1) выбираются различные простые числа и различные простые нечётные такие, что 1) для каждого все простые делители числа содержатся среди и не делятся на квадрат простого числа; 1) 2) для каждой пары выбранных чисел проводятся тесты, подобные сравнению из теоремы 3. Если не удовлетворяет какому-либо из этих тестов - оно составное. В противном случае 3) определяется не очень большое множество чисел, с которыми только и могут быть сравнимы простые делители числа должен удовлетворять сравнению вида , . 4) проверяется, содержит ли найденное множество делители - простое число. Если число составное, оно обязательно имеет простой делитель Сумма Якоби определяется для двух характеров модулю выполняется классическое соотношение связывающее суммы Гаусса с суммами Якоби и позволяющее переписать сравнение теоремы 3 в терминах сумм Якоби. Так. при и соответствующее сравнение, справедливое для простых где и - некоторый корень кубический из 1. В 1984 г. было внесено существенное усовершенствование в алгоритм, позволившее освободиться от требования неделимости чисел на квадраты простых чисел. В результате, например, выбрав число и взяв равным произведению простых чисел с условием, что делится на Персональный компьютер с процессором Pentium-150. пользуясь реализацией этого алгоритма на языке UBASIC, доказал простоту записываемого 65 десятичными знаками, большего из простых чисел в примере Ривеста, Шамира и Адлемана за 8 секунд. Сравнение этих 8 секунд и 17 лет, потребовавшихся для разложения на множители предложенного в примере числа, конечно, впечатляет. Отметим, что опенка сложности этого алгоритма представляет собой трудную задачу аналитической теории чисел. Как уже указывалось, количество операций оценивается величиной и и с вероятностью большей за арифметических операций. А в предположении расширенной гипотезы Римана эта опенка сложности может быть получена при эффективно указанных и 4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА Представленный выше алгоритм шифрования был реализован
Похожие работы
- Рефераты
- Контрольные