В реальных приложениях генерация простых чисел происходит быстро.
(1) Сгенерируйте случайное и-битовое число/;.
(2) Установите старший и младший биты равными 1. (Старший бит гарантирует требуемую длину простого числа, а младший бит обеспечивает его нечетность.)
(3) Убедитесь, что р не делится на небольшие простые числа: 3, 5, 7, 11, и т.д. Во многих реализациях пров е-ряется делимость р на все простые числа, меньшие 256. Наиболее эффективной является проверка на д е-лимость для всех простых чисел, меньших 2000 [949]. Это может быть эффективно выполнено с помощью колеса [863].
(4) Выполните тест Rabin-Miller для некоторого случайного а. Если р проходит тест, сгенерируйте другое случайное а и повторите проверку. Выбирайте небольшие значения а для ускорения вычислений. Выполните пять тестов [651]. (Одного может показаться достаточным, но выполните пять.) Если р не проходит одной из проверок, сгенерируйте другое р и попробуйте снова.
Иначе, можно не генерировать р случайным образом каждый раз, но последовательно перебирать числа, н а-чиная со случайно выбранного до тех пор, пока не б удет найдено простое число.
Этап (3) не является обязательным, но это хорошая идея. Проверка, что случайное нечетное р не делится на 3, 5 и 7 отсекает 54 процента нечетных чисел еще до этапа (4). Проверка делимости на все простые числа, меньшие 100, убирает 76 процентов нечетных чисел, проверка делимости на все простые числа, меньшие 256, убирает 80 процентов нечетных чисел. В общем случае, доля нечетных кандидатов, которые не делятся ни на одно простое число, меньшее и, равна 1.12/1п п. Чем больше проверяемое и, тем больше предварительных вычислений нужно выполнить до теста Rabin-Miller.
Одна из реализаций этого метода на Sparc II способна находить 256-битовые простые числа в среднем за 2.8 секунды, 512-битовые простые числа - в среднем за 24.0 секунды, 768-битовые простые числа - в среднем за 2.0 минуты, а 1024-битовые простые числа - в среднем за 5.1 минуты [918].