PDF книги

Поиcк по сайту by Google

Рейтинг@Mail.ru
Rambler's Top100
PDF книги » Информатика. Компьютеры » под общ. ред. В.В. Ященко - Введение в криптографию

под общ. ред. В.В. Ященко - Введение в криптографию

Скачать
Название: Введение в криптографию
Автор: под общ. ред. В.В. Ященко
Категория: Информатика. Компьютеры
Тип: Книга
Дата: 23.02.2009 19:25:41
Скачано: 250
Оценка:
Описание: Действительно, пусть N равняется произведению не менее двух простых чисел. Каждое из них, согласно утверждению теоремы 2, не меньше, чем 25 + 1. Но тогда (25 + I)2 ^ N = SR + 1 ^ 452 + 25 + 1. Противоречие и доказывает следствие. Покажем теперь, как с помощью последнего утверждения, имея большое простое число 5, можно построить существенно большее простое число N. Выберем для этого случайным образом четное число R на промежутке 5 ^ JR ^ 45 + 2 и положим N = SR + 1. Затем проверим число N на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем N некоторое количество раз с помощью алгоритма 5. Если при этом выяснится, что N — составное число, следует выбрать новое значение R и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число N, выдержавшее испытания алгоритмом 5 достаточно много раз. В этом случае появляется надежда на то, что N — простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2. Для этого можно случайным образом выбирать число а, 1 < а < N, и проверять для него выполнимость соотношений aN_1 = 1 (mod N), (aR -l,N) = 1. (12) Если при выбранном а эти соотношения выполняются, то, согласно следствию из теоремы 2, можно утверждать, что число N простое. Если же эти условия нарушаются, нужно выбрать другое значение а и повторять эти операции до тех пор, пока такое число не будет обнаружено. Предположим, что построенное число N действительно является простым. Зададимся вопросом, сколь долго придется перебирать числа а, пока не будет найдено такое, для которого будут выполнены условия (12). Заметим, что для простого числа N первое условие (12), согласно малой теореме Ферма, будет выполняться всегда. Те же числа а, для которых нарушается второе условие (12), удовлетворяют сравнению аи = 1 (mod N). Как известно, уравнение xR = 1 в поле вычетов Fn имеет не более R решений. Одно из них х = 1. Поэтому на промежутке 1 < а < N имеется не более if? — 1 чисел, для которых не выполняются условия (12). Это означает, что, выбирая случайным образом числа а на промежутке 1 < а < N, при простом N можно с вероятностью большей, чем 1 — 0(5-1), найти число а, для которого будут выполнены условия теоремы 2, и тем доказать, что N действительно является простым числом. Заметим, что построенное таким способом простое число N будет удовлетворять неравенству N > 52, т. е. будет записываться вдвое большим количеством цифр, чем исходное простое число 5. Заменив теперь число 5 на найденное простое число N и повторив с этим но-
Файл: 1.60 МБ
Скачать