Простое детерминированное тестирование простоты для малых чисел

Question

Мне известно, что на практике используется ряд алгоритмов тестирования простоты (сито Эратосфена, тест Ферма, Миллер-Рабин, АКС и т. Д.). Однако они являются либо медленными (например, сито), вероятностными (Ферма и Миллера-Рабина), либо относительно сложными для реализации (АКС).

Какое лучшее детерминированное решение для определения, является ли число простым?

Обратите внимание, что я в первую очередь (каламбур) заинтересован в проверке чисел порядка 32 (и, возможно, 64) бит. Таким образом, надежное решение (применимо к большим числам) не требуется.

Answer 1

До ~2^30 вы можете грубой силой с пробным делением.

До 3.4*10^14, Рабин-Миллер с первыми 7 простыми числами доказал свою детерминированность .

Кроме того, ты сам по себе. Не существует известного субкубического детерминированного алгоритма.

РЕДАКТИРОВАТЬ: Я помнил это, но я не нашел ссылку до сих пор:

http://reference.wolfram.com/legacy/v5_2/book/section-A.9.4

PrimeQ сначала проверяет делимость с использованием небольших простых чисел, затем использует Миллер-Рабин сильный псевдопригодный тест базы 2 и базы 3, а затем использует тест Лукаса.

Начиная с 1997 года, эта процедура, как известно, является правильной только для n < 10^16, и вполне возможно, что для больших n он может претендовать на композит число должно быть простым.

Так что если вы реализуете Рабина-Миллера и Лукаса, у вас все хорошо до 10 ^ 16 .

Answer 2

Если бы меня не волновало пространство, я бы попытался предварительно вычислить все простые числа ниже 2 ^ 32 (~ 4e9 / ln (4e9) * 4 байта, что меньше 1 ГБ), сохранить их в памяти и использоватьбинарный поиск.Вы также можете поиграть с отображением в памяти файла, содержащего эти предварительно вычисленные простые числа (плюсы: более быстрый запуск программы, минусы: будут медленными, пока все необходимые данные не окажутся в памяти).

Answer 3

Если вы можете вычислить n -1, легко доказать, что n - простое число, используя метод, разработанный Эдуардом Лукасом в 19 веке.Вы можете прочитать об алгоритме в Википедии или посмотреть мою реализацию алгоритма в моем блоге .Существуют варианты алгоритма, которые требуют только частичной факторизации.

Если факторизация n -1 затруднительна, лучшим методом является доказательство примитивности эллиптической кривой алгоритм, но это требует больше математики и больше кода, чем вы, возможно, захотите написать.В любом случае это будет намного быстрее, чем у AKS.

Вы уверены, что вам нужно абсолютное доказательство первичности?Алгоритм Baillie-Wagstaff работает быстрее, чем любой детерминистский доказатель первичности, и нет известных контрпримеров.

Если вы знаете, что n никогда не превысит 2 ^64 сильных псевдопростых тестов с использованием первых двенадцати простых чисел в качестве баз достаточно для доказательства n простого числа.Для 32-разрядных целых чисел достаточно строгих псевдо-простых тестов для трех оснований 2, 7 и 61, чтобы доказать первичность.

Answer 4

1. Используйте сито Эратосфена, чтобы предварительно рассчитать столько простых чисел, сколько у вас есть места.Вы можете вписать много в один бит на число и разделить пополам пространство, только пропуская нечетные числа (рассматривая 2 как особый случай).

2. Для чисел от Sieve.MAX_NUM до квадрата Sieve.MAX_NUM вы можете использовать пробное деление, поскольку у вас уже есть требуемые простые числа.Разумное использование Миллера-Рабина с более крупными неосновными остатками может значительно ускорить процесс.

3. Для чисел, превышающих это, я бы использовал один из вероятностных тестов, Миллер-Рабин хорош, и если повторение несколько раз может дать результаты, которые с меньшей вероятностью будут ошибочными, чем аппаратное обеспечениесбой в компьютере, на котором вы работаете.