Самый быстрый алгоритм для [закрытого] теста простоты чисел

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

Обратите внимание, что вероятность ложных срабатываний (нет ложноотрицательных результатов) может быть сколь угодно малой путем повторения теста.

Взгляните на мой ответ здесь:

как проверить простое число длиной 1000 цифр?

Тест выполняется очень быстро. Если вы работаете в 64-битном или меньшем диапазоне, вы можете добавить GCD с 30030, чтобы сэкономить немного времени для большинства чисел.

Быстрее всего, вероятно, будет поискать его в предварительно вычисленном списке простых чисел. См. здесь, например, , у них до 2 ^ 43112609-1 (наибольшее известное простое число).

Если вы хотите проверить простоту long long, тогда хороший выбор Baillie PSW test . Этот тест выполняет один строгий тест псевдопроста и один тест Лукаса и, следовательно, очень быстрый. Ожидается, что существуют некоторые композиты, которые проходят этот тест, но пока ни один из них не известен, и, конечно же, нет исключения ниже 10 ¹⁵ . Вариант этого теста, например, используется в системе Mathematica.

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

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

Подождите - мне просто нужно закрыть окно, над головой столько черных вертолетов ........

(Или посмотрите на Как проверить на первичность?)

Я бы предложил библиотеку GNU MP , которая использует алгоритм Миллера-Рабина . Я использую его несколько месяцев, и он очень быстрый.

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

Я считаю, что асимптотически самым быстрым текущим (недоверчиво) тестом первичности является «улучшенный AKS Ленстра/Померанс», который имеет сложность, которая по существу O(n^6).

Однако диапазон long (предполагая типичную систему, где это 64-битное целое число) на самом деле не так велик. В частности, существует только ~ 200 миллионов простых чисел меньше 2^32, поэтому использование быстрого вероятностного теста, за которым следует пробное деление с предварительно вычисленным списком простых чисел (или просто поиск числа в списке простых чисел, если он у вас есть), было бы чертовски быстрым в этом диапазоне, и, вероятно, это правильный способ сделать это.