Я знаю, что на практике используется ряд алгоритмов проверки простоты (сито Эратосфена, тест Ферма, Миллера-Рабина, AKS и т. Д.). Однако они либо медленные (например, сито), либо вероятностные (Ферма и Миллер-Рабин), либо относительно трудные для реализации (AKS).
Каково наилучшее детерминированное решение для определения того, является ли число простым?
Обратите внимание, что меня в первую очередь (каламбур) интересует тестирование чисел порядка 32 (а может быть, 64) битов. Поэтому надежное решение (применимое к большим числам) не требуется.