Практические соображения

В реальных приложениях генерация простых чисел происходит быстро.

1. Сгенерируйте случайное n-битовое число p.

2. Установите старший и младший биты равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший бит обеспечивает его нечетность.)

3. Убедитесь, что p не делится на небольшие простые числа: 3, 5, 7, 11, и т.д. Во многих реализациях проверяется делимость p на все простые числа, меньшие 256. Наиболее эффективной является проверка на делимость для всех простых чисел, меньших 2000.

4. Выполните тест Rabin-Miller для некоторого случайного a. Если p проходит тест, сгенерируйте другое случайное a и повторите проверку. Выбирайте небольшие значения a для ускорения вычислений. Выполните пять тестов. (Одного может показаться достаточным, но выполните пять.) Если p не проходит одной из проверок, сгенерируйте другое p и попробуйте снова.

Иначе, можно не генерировать p случайным образом каждый раз, но последовательно перебирать числа, начиная со случайно выбранного до тех пор, пока не будет найдено простое число.

Этап (3) не является обязательным, но это хорошая идея. Проверка, что случайное нечетное p не делится на 3, 5 и 7 отсекает 54 процента нечетных чисел еще до этапа (4). Проверка делимости на все простые числа, меньшие 100, убирает 76 процентов нечетных чисел, проверка делимости на все простые числа, меньшие 256, убирает 80 процентов нечетных чисел. В общем случае, доля нечетных кандидатов, которые не делятся ни на одно простое число, меньшее n, равна 1.12/ln n. Чем больше проверяемое n, тем больше предварительных вычислений нужно выполнить до теста Rabin-Miller.

Список литературы

1. Ю. Лифшиц. Курс лекций «Современные задачи криптографии». Доступно в электронной форме по адресу http://yury.name/cryptography

2. Шнайер Б. Прикладная криптография.- М. : Триумф, 2002. – 816с.

3. Erich Wegener, Mario Werner. «Evaluating 16-bit Processors for Elliptic Curve Cryptography». Institute for Applied Information Processing And Communications (IAIK), Graz University of Technology

4. http://old.pgpru.com/pgp_for_beginners/pgp_for_beg_01.htm

5. https://www.gpg4win.org/

6. http://jenyay.net/blog/2012/01/04/shifrovanie-s-pomoshhyu-gnupg-dlya-polzovatelejj/

28