Быстрый тест на простоту со 100% уверенностью?

Как правило, 100% -ная уверенность невозможна на физическом компьютере, поскольку существует небольшая, но ограниченная вероятность того, что какой-либо компонент невидимым образом вышел из строя и что ответ, приведенный в конце, неверен. Учитывая этот факт, вы можете запустить достаточно вероятностные тесты Миллера-Рабина, чтобы вероятность того, что число будет составным, намного меньше вероятности отказа вашего оборудования. Нетрудно проверить уровень достоверности 1 к 2 ^ 256:

boolean isPrime(num)
limit <- 256
certainty <- 0
while (certainty < limit)
if (millerRabin returns notPrime)
return false
exit
else
certainty <- certainty + 2
endif
endwhile
return true
end isPrime

Это проверит, что число простое, с точностью до 1 в 2 ^ 256. Каждый M-R тест добавляет коэффициент четыре к достоверности. Я видел полученные в результате простые числа, называемые «простыми числами промышленной силы», которые достаточно хороши для всех практических целей, но не совсем для теоретической математической определенности.

Для маленьких N, пробные работы отдела; предел там, вероятно, где-то около 10 ^ 12. Для несколько большего N, Существуют различные исследования (см. работы Герхарда Яешке и Чжоу Чжана), которые вычисляют наименьшее количество псевдоприм для различных коллекций оснований Миллера-Рабина; это приведет вас к 10 ^ 25. После этого все становится сложнее.

«Большие орудия» доказательства простоты — это метод APRCL (его можно назвать суммами Якоби или гауссовскими суммами) и метод ECPP (основанный на эллиптических кривых). Оба являются сложными, поэтому вы захотите найти реализацию, а не писать свою собственную. Эти методы могут обрабатывать числа из нескольких сотен цифр.

Метод AKS доказан за полиномиальное время и прост в реализации, но константа пропорциональности очень высока, поэтому на практике он бесполезен.

Если вы можете фактор N-1, или даже частично его учесть, метод Поклингтона может определить первичность N. Сам метод Поклингтона быстрый, но факторинг может и не быть.

Для всего этого вы должны быть достаточно уверены, что число простое, прежде чем пытаться доказать это. Если ваше число не простое, все эти методы будут правильно определять это, но сначала они будут тратить много времени, пытаясь доказать, что составное число простое.

У меня есть реализации АКС а также Pocklington в моем блоге.

Метод доказательства зависит от типа простого числа, которое вы пытаетесь доказать (например, у простых чисел Мерсенна есть специальные методы доказательства простоты, которые работают только с ними) и размера в десятичных разрядах. Если вы смотрите на сотни цифр, то есть только одно решение, хотя и неадекватное: алгоритм AKS. Это, конечно, быстрее, чем другие алгоритмы доказательства простоты для достаточно больших простых чисел, но к тому времени, когда это станет полезным, это займет так много времени, что это действительно не стоит проблем.

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

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