Я ищу алгоритм для теста на простоту большого (например, 10) номеров. Есть ли хорошие алгоритмы?Детерминистически проверяет, является ли большое число простым или составным?
В идеале, я бы предпочел алгоритм, который не является сомнительным.
Примечание: номера имеют более 50 и менее 200 цифр.
Если вы ищете, не вероятностный тест, вы можете проверить AKS primality testing algorithm, которая проходит в примерно O (журнал п). Для количества цифр, которое у вас есть, это, вероятно, возможно.
Это говорит о том, что тесты на предвзятость являются чрезвычайно хорошими, и многие из них имеют экспоненциально небольшие коэффициенты ошибок. Я бы предложил использовать один из них, если нет веской причины не делать этого.
EDIT: Я только что нашел this page containing several C++ implementations of AKS. Я понятия не имею, работают ли они правильно или нет, но они могут быть хорошей отправной точкой.
Надеюсь, это поможет!
об алгоритме AKS: Этот алгоритм использует функции log() и sqrt() для больших чисел (например, 10^200). это дорого для реализации. пробные тесты хороши, спасибо! я буду использовать его! – gaussblurinc
Насколько дорого можно вычислить 'sqrt (10^200)'? –
Обычно мы использовали бы вероятный простой тест. Я рекомендую BPSW, на котором вы можете следить за тестом Frobenius и/или некоторыми случайными вычислениями Миллера-Рабина, если вы хотите больше уверенности. Это будет быстро и, возможно, больше, чем выполнение некоторых доказательств.
Предположим, вы говорите, что это недостаточно. Тогда вы действительно хотите использовать 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 или около того цифры быстрее, и у него есть лучший наклон. Это программа выбора для больших входов (2000-30 000 цифр).
Просто посмотреть его на википедии.Но я бы, вероятно, использовал вероятностный алгоритм. Вы можете получить вероятность ошибки экспоненциально малой, так что вероятность ошибки из-за самого теста мала по сравнению с шансом аппаратных ошибок. – CodesInChaos