Ищем быстрый детерминист

Question

Я искал способы определить, является ли число простым или нет, но большинство способов либо вероятностные c (Миллер Рабин), либо для чисел, меньших 64 бит.

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

Answer 1

Я предполагаю, что вы хотите получить доказуемо правильный ответ, а не избегать случайности в целом.

1. Выполните несколько раундов теста первичности Миллера-Рабина. Если это не удается, вы знаете, что число составное, и все готово.
2. Факторизация n-1. Для этого простейшим является алгоритм Ро Полларда. Если это недостаточно быстро, используйте Quadrati c Sieve.
3. Проверьте, являются ли факторы простыми, рекурсивно используя тот же подход. Если они составные, продолжайте их разлагать на множители.
4. Используйте тест примитивности Лукаса: попытайтесь найти генератор мультипликативной группы по модулю n порядка n-1. Выберите случайное число a, убедитесь, что a ^ (n-1) = 1 (mod n) и что a ^ ((n-1) / p) ≠ 1 (mod n) для всех простых факторов p из n-1 , Если это так, a - это генератор, а n - это простое число, поэтому вы можете сделать это.
5. Если n - простое число, вероятность успеха в поиске генератора равна (1-1 / p ₁ ) (1-1 / p ₂ ) ... где p ₁ , p ₂ , ... - различные простые числа факторы н-1. Это как минимум 1 / O (log log n). Поэтому после попытки O (log log n) вы должны доказать, что n - простое число.
6. Если вам все еще не удается доказать, что n простое, go вернитесь к шагу 1. Возможно, это все-таки составное.

Answer 2

То, что вы ищете, не существует. Не существует простого критерия c примитивности детерминированности, который бы работал всегда для всех диапазонов целых чисел.

Вы уже знаете о тесте Миллера-Рабина. Это можно сделать детерминированными c на определенных диапазонах; см. здесь или здесь для деталей. Если вы принимаете гипотезу Римана, то n является простым, если n является a -SPRP (псевдосилом Миллера) для всех целых чисел a с 1 <<em> a <2 (log <em>n ) ². Аналогичным и несколько лучшим тестом является тест Baill ie -Wagstaff; оно не является детерминированным c, но сбои не известны.

Для чисел n до 2 ¹²⁸ , не слишком сложно вычислить n - 1 и используйте критерий Поклингтона для доказательства простоты. Вы можете использовать пробное деление, или Pollard rho, или ECM для выполнения факторизации. Есть также тесты ( BLS75 ), которые могут доказать простоту на основе частичной факторизации. Большие n также могут быть проверены как простые с помощью критерия Поклингтона, хотя иногда факторизация становится трудной.

Для n до приблизительно 10 ¹⁰⁰⁰ быстрое простое тестирование E CPP не является необоснованным, хотя для больших чисел в этом диапазоне это может занять некоторое время. Кроме того, если ваш номер не имеет особой формы, вам почти не повезло.