Применение алгоритма RSA для шифрования потоков данных — страница 11

  • Просмотров 7970
  • Скачиваний 308
  • Размер файла 89
    Кб

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

Несмотря на отсутствие оценок сложности, на практике он работает вполне удовле­творительно. 3.2. Нахождение больших простых чисел Конечно же, большие простые числа можно строить сравнительно быстро. При этом можно обеспечить их случайное распределение в заданном диапазоне величин. В противном случае теряла бы всякий практический смысл система шифрования RSA. Наиболее эффективным средством построения простых чисел является

несколько модифицированная малая теорема Ферма. Теорема 2. Пусть - нечётные натуральные числа, числа существует целое число такое, что (10) Тогда каждый простой делитель числа удовлетворяет сравнению Доказательство. Пусть - простой делитель числа a - не­который делитель спра­ведливы соотношения (11) Обозначим буквой порядок элемента в мультипликативной группе поля входит в раз­ложение на простые множители числа в степени такой

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

отсутствие малых простых делителей, разделив его на малые простые числа; испытаем некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что - составное число, следует выбрать новое значение и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2. Для этого можно случайным образом выбирать число . (12)

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