Интернет магазин китайских планшетных компьютеров

Компьютеры - Случайное простое число - Требования к алгоритму и его реализации

Требования к алгоритмам генерации случайных простых чисел сводятся к следующим двум:

• Распределение получаемых простых чисел должно быть близко к равномерному на множестве всех простых чисел, содержащих k битов. Существует несколько способов обеспечить выполнимость этого требования.
• Процесс генерации конкретного случайного простого числа нельзя воспроизвести, даже зная детали алгоритма и его реализации. Обычно выполнение этого требования обеспечивается использованием криптостойкого ГПСЧ, проинициализированного некоторым ключом, получаемым извне. В качестве ключа может выступать, например, значение криптографической хеш-функции от секретной фразы, запрашиваемой у пользователя.

Типовые алгоритмы генерации случайных простых чисел

Везде далее предполагается использование криптографически стойкого ГПСЧ, проинициализированного с помощью секретного ключа.

Тестирование простоты

Проверить простоту числа p, содержащего k битов, можно так:

1. Убедиться, что p не делится на небольшие простые числа 3, 5, 7, 11, и т.д. до некоторого небольшого предела. Такая проверка позволяет эффективно отсечь множество заведомо составных чисел, прежде чем проверять их посредством более трудоёмких алгоритмов. Так, проверка делимости p на простые числа 2, 3, 5 и 7 отсеивает все четные числа и 54% нечетных чисел, проверка делимости p на все простые числа до 100 отсеивает 76% нечетных чисел, а проверка делимости p на все простые числа до 256 отсеивает 80% нечетных чисел.
2. Выполнить тест Миллера — Рабина с количеством раундов не меньше k.

Если число p не проходит хотя бы одной проверки — оно не является простым. В противном случае с большой вероятностью число p является простым.

Типовой алгоритм 1

1. Сгенерировать k − 1 случайных битов и составить из них k-битное число p.
2. Увеличить p на 1 и проверить его простоту. Повторять этот шаг до тех пор, пока не будет найдено простое число.

Второй шаг можно ускорить, если рассматривать только нечетные числа или числа сравнимые с 1 и 5 по модулю 6 и т.п.

Типовой алгоритм 2

Этот алгоритм описан в книге «Введение в криптографию» под редакцией В. В. Ященко.