Не могли бы вы предложить быстрый, детерминированный метод, который можно использовать на практике для тестирования, если большое число является простым или нет?
Кроме того, я хотел бы знать, как правильно использовать недетерминированные тесты правильности. Например, если я использую такой метод, я могу быть уверен, что число не является простым, если вывод "нет", но как насчет другого случая, когда вывод "возможно"? Нужно ли в этом случае проверять правильность вручную?
Спасибо заранее.
Единственный детерминированный алгоритм полиномиального времени для проверки примитивности, о котором я знаю, - это тест примитивности AKS (http://en.wikipedia.org/wiki/AKS_primality_test). Тем не менее, существует очень много рандомизированных рандомизированных тестов, которые бывают быстрыми и имеют очень хорошую вероятность успеха. Они обычно работают, обнаруживая, является ли число составным с экспоненциально хорошей вероятностью, поэтому они либо сообщают, что число является составным, либо потребуют от вас сказать "возможно" с очень хорошей уверенностью.
"Вероятно" на самом деле означает 1-ε, а ε становится настолько маленьким, насколько вам нужно.
Большинство приложений имеют некоторую небольшую, но отличную от нуля вероятность сбоя, которая не связана с тестированием примитивов, например
в криптографических приложениях, злоумышленник, надеясь угадать секрет, например, вероятность 2 ^ (- 100)
аппаратный сбой (вызванный излучением) случайным образом переворачивает бит вашего компьютера (возможно, тот, который содержит результат вашего "детерминированного" теста на соответствие)
(действительно, более вероятно, чем другие типы сбоев)
Таким образом, нажимаем ε на этот порядок величины на практике.
Например, OpenSSL, GnuPG используют только не детерминированный тест простоты. "Вероятно", вы действительно не хотите детерминированного теста. Но проверьте, что доступно для вас: если у вас есть какие-либо библиотеки под рукой, и они выполняют достаточно - продолжайте и используйте их.
Если вы хотите найти случайное число для использования в ключах RSA, сначала вы должны использовать вероятностный тест. Если вероятность достаточно высока для ваших нужд, тогда остановитесь там. Если вы должны быть уверены, то, как только вы найдете большое случайное вероятное-простое, проверьте его с помощью AKS или другого невариантного теста. Это позволяет быстро проверять множество простых чисел, будучи уверенным, когда вы думаете, что нашли его.
Если вы пытаетесь проверить, что конкретный существующий номер является простым, вы должны использовать один из тестов, который отвечает с уверенностью. Существуют и другие не-полиномиальные тесты времени, используйте тот, который на практике быстрее всего.