Самый быстрый тест на простоту

Question

Не могли бы вы предложить быстрый, детерминированный метод, который можно использовать на практике, для проверки, является ли большое число простым или нет?

Кроме того, я хотел бы знать, как правильно использовать недетерминированные тесты простоты. Например, если я использую такой метод, я могу быть уверен, что число не простое, если на выходе «нет», но как насчет другого случая, когда на выходе «вероятно»? Нужно ли вручную проверять первичность в этом случае?

Спасибо заранее.

Answer 1

«Вероятно» на самом деле означает 1-ε, а ε становится настолько маленьким, насколько вам нужно.

У большинства приложений есть небольшая, но ненулевая вероятность сбоя, которая не связана с проверкой простоты, например

• в криптографических приложениях, злоумышленник, к счастью, угадывает секрет, например, вероятность 2 ^ (- 100)

• аппаратный сбой (вызванный излучением), случайным образом отражающий некоторую часть памяти вашего компьютера (возможно, тот, который содержит выходные данные вашего "детерминированного" теста на простоту

• ошибки (более вероятные, чем у других типов ошибок)

Таким образом, нажатие ε до такого порядка будет достаточным на практике.

Например, OpenSSL, GnuPG используют только недетерминированный тест на простоту. «Вероятно», вы действительно не хотите никакого детерминированного теста. Но проверьте, что вам доступно: если у вас есть какие-либо библиотеки под рукой, и они работают достаточно - продолжайте и используйте их.

Answer 2

Единственный детерминированный алгоритм полиномиального времени для тестирования простоты, о котором я знаю, - это тест простоты AKS (http://en.wikipedia.org/wiki/AKS_primality_test).. Однако существует много очень хороших рандомизированных тестов простоты, которые бывают быстрыми и имеют чрезвычайно высокую вероятность Обычно они работают, находя, является ли число составным с экспоненциально хорошей вероятностью, поэтому они либо сообщают, что число составное, либо потребуют, чтобы вы сказали «возможно» с очень хорошей достоверностью.

Answer 3

Если вы ищете случайное простое число для использования в ключах RSA, вам следует сначала использовать вероятностный тест. Если вероятность достаточно высока для ваших нужд, остановитесь на этом. Если вы должны быть уверены, то, как только вы найдете большое случайное вероятное простое число, проверьте его с помощью AKS или другого не вероятностного теста. Это позволяет быстро проверить множество простых чисел, будучи уверенным в том, что вы нашли один из них.

Если вы пытаетесь проверить, является ли конкретное существующее число простым, то вам следует использовать один из тестов, который отвечает с уверенностью. Существуют и другие неполиномиальные тесты, используйте самый быстрый на практике.