Детерминистская проверка, является ли большое число простым или составным?

Question

Я ищу алгоритм проверки простоты больших (например, 10 ²⁰⁰ ) чисел. Есть ли хорошие алгоритмы?

В идеале, я бы предпочел алгоритм, который не является вероятностным.

Примечание. Номера состоят из 50 и менее 200 цифр.

Answer 1

Если вы ищете не вероятностный тест, вы можете попробовать алгоритм тестирования простоты AKS , который работает примерно за O (log ⁶ n) времени , Для количества имеющихся у вас цифр это возможно.

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

EDIT : я только что нашел эту страницу, содержащую несколько реализаций CKS AKS на C ++. Я понятия не имею, работают ли они правильно или нет, но они могут быть хорошей отправной точкой.

Надеюсь, это поможет!

Answer 2

Как правило, мы будем использовать вероятный простой тест. Я рекомендую BPSW , за которым вы можете выполнить тест Фробениуса и / или некоторые случайные базовые тесты Миллера-Рабина, если вы хотите большей уверенности. Это будет быстро и возможно более наверняка, чем запуск некоторых проверочных реализаций.

Предположим, вы говорите, что этого недостаточно. Тогда вы действительно хотите использовать ECPP и получить сертификат. Разумные реализации: Primo или ecpp-dj . Они могут доказать первичность 200-значных чисел с точностью до секунды и вернуть сертификат, который можно проверить независимо.

APR-CL - еще один разумный метод. Недостатком является то, что он не возвращает сертификат, поэтому вы доверяете реализации - вы получаете вывод «да» или «нет», который является детерминистически правильным, если реализация была правильной. Pari / GP использует APR-CL со своей командой isprime, а Дэвид Кливер имеет отличную реализацию с открытым исходным кодом: mpz_aprcl . У этих реализаций был некоторый обзор кода и ежедневное использование в различном программном обеспечении, поэтому должно быть хорошо.

AKS - ужасный метод для применения на практике. Он не возвращает сертификат, и не так сложно найти испорченные реализации, которые полностью лишают смысла использовать проверочный метод по сравнению с хорошими вероятными простыми тестами. Это также ужасно медленно. 200-значные числа намного превосходят практическую точку зрения для любой реализации, о которой я знаю. В ранее упомянутом программном обеспечении ecpp-dj есть «быстрый», так что вы можете попробовать его, и есть немало других реализаций, которые можно найти.

Для некоторого представления о скорости, вот времена некоторых реализаций. Я не знаю каких-либо реализаций AKS, APR-CL или BPSW, которые бы быстрее, чем показанные (пожалуйста, прокомментируйте, если вы знаете одну). Primo начинается немного медленнее, чем показанный ecpp-dj, но при 500 или более разрядах он быстрее и имеет больший уклон, чем раньше. Это программа выбора для больших вводов (от 2 000 до 30 000 цифр).