Применение алгоритма RSA для шифрования потоков данных — страница 11
помощью расширенной гипотезы Римана доказал, что для каждого простого числа существует квадратичный невычет и Алгоритм Миллера принципиально отличается от алгоритма 2.1., так как полученное с его помощью утверждение о том, что число - составное, опирается на недоказанную расширенную гипотезу Римана и потому может быть неверным. В то время как вероятностный алгоритм 2.1. даёт совершенно правильный ответ для составных чисел. Несмотря на отсутствие оценок сложности, на практике он работает вполне удовлетворительно. 3.2. Нахождение больших простых чисел Конечно же, большие простые числа можно строить сравнительно быстро. При этом можно обеспечить их случайное распределение в заданном диапазоне величин. В противном случае теряла бы всякий практический смысл система шифрования RSA. Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма. Теорема 2. Пусть - нечётные натуральные числа, числа существует целое число такое, что (10) Тогда каждый простой делитель числа удовлетворяет сравнению Доказательство. Пусть - простой делитель числа a - некоторый делитель справедливы соотношения (11) Обозначим буквой порядок элемента в мультипликативной группе поля входит в разложение на простые множители числа в степени такой же, как и в разложение делится на входит в разложение в степени не меньшей, чем в делится на четно. Теорема 2 доказана. Следствие. Если выполнены условия теоремы 2 и - простое число. Действительно, пусть равняется произведению не менее двух простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем Покажем теперь, как с помощью последнего утверждения, имея большое простое число на промежутке и положим на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что - составное число, следует выбрать новое значение и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2. Для этого можно случайным образом выбирать число . (12) Если при выбранном эти соотношения выполняются, то, согласно следствию из теоремы 2, можно утверждать, что число простое. Если же эти условия нарушаются, нужно выбрать другое значение и повторять эти операции до тех пор, пока такое число не будет обнаружено. Предположим, что построенное число действительно является простым. Зададимся вопросом, сколь долго придётся перебирать числа первое условие (12), согласно малой теореме
Похожие работы
- Рефераты
- Контрольные