Когда тест на первичность AKS действительно быстрее, чем другие тесты?

24

Я пытаюсь получить представление о том, как следует интерпретировать тест простоты AKS, когда узнаю о нем, например, следствие для доказательства того, что PRIMES ⊆ P, или действительно практичный алгоритм тестирования простоты на компьютерах.

Тест имеет полиномиальное время выполнения, но с высокой степенью и возможными высокими константами. Итак, в практическом смысле, при котором n превосходит другие тесты простоты? Здесь n - это число цифр простого числа, а «превосходит» относится к приблизительному времени выполнения тестов на типичных компьютерных архитектурах.

Меня интересуют функционально сопоставимые алгоритмы, то есть детерминированные, которые не нуждаются в гипотезах для корректности.

Кроме того, практично ли использование такого теста над другими с учетом требований к памяти?

Vortico
источник

Ответы:

23

Быстрый ответ: Никогда, в практических целях. В настоящее время он не имеет практического применения.

Измеренное время первичности

Во-первых, давайте отделим «практическое» тестирование композитности от доказательств простоты. Первый достаточно хорош для почти всех целей, хотя существуют разные уровни тестирования, которые люди считают адекватными. Для чисел ниже 2 ^ 64 для детерминистического ответа требуется не более 7 тестов Миллера-Рабина или один тест BPSW. Это будет намного быстрее, чем AKS, и будет одинаково верным во всех случаях. Для чисел больше 2 ^ 64 BPSW является хорошим выбором, поскольку некоторые дополнительные тесты Миллера-Рабина с произвольной базой добавляют дополнительную уверенность при очень небольших затратах. Почти все методы доказательства начинаются (или должны) с такого теста, потому что он дешевый и означает, что мы выполняем тяжелую работу только с числами, которые почти наверняка просты.

Переходя к доказательствам. В каждом случае полученное доказательство не требует предположений, поэтому их можно сравнить функционально. «Гоча» APR-CL состоит в том, что он не совсем полиномиален, а «гоча» ECPP / fastECPP заключается в том, что могут существовать числа, которые занимают больше времени, чем ожидалось.

На графике мы видим две реализации AKS с открытым исходным кодом - первая из статьи v6, вторая, включающая в себя улучшения от Бернштейна и Волоха и хорошую эвакуацию r / s от Борнемана. Они используют двоичную сегментацию в GMP для умножения полиномов, поэтому они довольно эффективны, и использование памяти не является проблемой для рассматриваемых здесь размеров. Они создают хорошие прямые линии с наклоном ~ 6,4 на графике log-log, и это здорово. Но экстраполяция до 1000 цифр происходит в расчетное время от сотен тысяч до миллионов лет, в отличие от нескольких минут для APR-CL и ECPP. Есть дальнейшая оптимизация, которую можно было бы сделать из статьи Бернштейна 2002 года, но я не думаю, что это существенно изменит ситуацию (хотя до ее реализации это не доказано).

В конце концов АКС превосходит пробный дивизион. Метод теоремы 5 BLS75 (например, доказательство n-1) требует частичного факторинга n-1. Это прекрасно работает при небольших размерах, а также, когда нам везет, а n-1 легко вычислить, но в конечном итоге мы застрянем, когда нужно составить множитель большого полу-простого числа. Существуют более эффективные реализации, но они не масштабируются за последние 100 цифр. Мы видим, что AKS пройдет этот метод. Таким образом, если вы задали вопрос в 1975 году (и тогда у него был алгоритм AKS), мы могли бы рассчитать кроссовер, для которого AKS был наиболее практичным алгоритмом. Но к концу 1980-х годов APR-CL и другие циклотомические методы были верным сравнением, и к середине 1990-х мы должны были бы включить ECPP.

logloglognO(log5+ϵ(n))O(log4+ϵ(n))

O(log4+ϵ(n))(lgn)4+o(1)(lgn)4+o(1)

Некоторые из этих алгоритмов могут быть легко распараллелены или распределены. AKS очень легко (каждый тест независимый). ECPP не слишком сложен. Я не уверен насчет APR-CL.

Методы ECPP и BLS75 создают сертификаты, которые можно независимо и быстро проверить. Это огромное преимущество перед AKS и APR-CL, где мы просто должны доверять реализации и компьютеру, который ее произвел.

DanaJ
источник
18

O~(log6n)O~(log4n)O~(n1/7)O(lognO(logloglogn))

O~(log2n)280O~(log2n)

Во всех этих тестах память не является проблемой.


В своем комментарии jbapple поднимает вопрос о том, какой тест на простоту использовать на практике. Это вопрос реализации и бенчмаркинга: внедрить и оптимизировать несколько алгоритмов и экспериментально определить, какой из них наиболее быстрый в каком диапазоне. Для любопытных кодеры PARI сделали именно это, и они придумали детерминированную функцию isprimeи вероятностную функцию ispseudoprime, обе из которых можно найти здесь . Используется вероятностный тест Миллера-Рабина. Детерминированный - это BPSW.


Вот больше информации от Даны Якобсен :

Pari, начиная с версии 2.3, использует доказательство первичности APR-CL для isprime(x)и вероятное простое испытание BPSW (с «почти сверхсильным» тестом Лукаса) для ispseudoprime(x).

Они принимают аргументы, которые меняют поведение:

  • isprime(x,0) (по умолчанию.) Используется комбинация (BPSW, быстрая теорема Поклингтона или BLS75 5, APR-CL).
  • isprime(x,1)n1
  • isprime(x,2) Использует APR-CL.

  • ispseudoprime(x,0) (по умолчанию.) Использует BPSW (MR с базой 2, «почти сверхсильный» Лукас).

  • ispseudoprime(x,k)k1kmpz_is_probab_prime_p(x,k)

Пари 2.1.7 использовал намного худшую установку. isprime(x)это были просто тесты МР (по умолчанию 10), которые приводили к забавным вещам, таким как isprime(9)возвращение истины довольно часто. Использование isprime(x,1)сделало бы доказательство Pocklington, которое было хорошо для приблизительно 80 цифр и затем стало слишком медленным, чтобы быть вообще полезным.

Вы также пишете, что на самом деле никто не использует эти алгоритмы, так как они слишком медленные. Я думаю, я знаю, что вы имеете в виду, но я думаю, что это слишком сильно в зависимости от вашей аудитории. AKS, конечно, невероятно медленный, но APR-CL и ECPP достаточно быстрые, чтобы их использовали некоторые люди. Они полезны для параноидальной криптографии и полезны для людей, которые делают что-то вроде primegapsили factordbкогда у человека достаточно времени, чтобы получить проверенные простые числа.

[Мой комментарий по этому поводу: при поиске простого числа в определенном диапазоне мы используем некоторый метод просеивания, за которым следуют некоторые относительно быстрые вероятностные тесты. Только тогда, если вообще, мы запускаем детерминированный тест.]

Во всех этих тестах память не является проблемой. Это проблема для АКС. Посмотрите, например, этот eprint . Отчасти это зависит от реализации. Если кто-то реализует то, что видео Numberphile называет AKS (что на самом деле является обобщением Маленькой теоремы Ферма), использование памяти будет чрезвычайно высоким. Использование NTL-реализации алгоритма v1 или v6, такого как упомянутая статья, приведет к глупым большим объемам памяти. Хорошая реализация GMP v6 по-прежнему будет использовать ~ 2 ГБ для 1024-битного простого числа, что очень многопамяти для такого небольшого числа. Использование некоторых улучшений Бернштейна и двоичной сегментации GMP приводит к гораздо лучшему росту (например, ~ 120 МБ для 1024-битных). Это все еще намного больше, чем нужно другим методам, и неудивительно, что оно будет в миллионы раз медленнее, чем APR-CL или ECPP.

Юваль Фильмус
источник
2
Я не верю, что это отвечает на поставленный вопрос, который потребовал бы вычисления констант этих тестов.
jbapple
1
Используйте свои отрицательные отзывы всякий раз, когда вы сталкиваетесь с вопиюще небрежным постом без усилий или ответом, который явно и, возможно, опасно неверен. - Я не вижу, как человек, голосующий против этого ответа, оправдывает голосование.
Пол GD
2
n
nlogn
Хороший пост, но ваше определение "никто" очень немного не соответствует. Из любопытства я проверил, сколько времени требуется для проверки вероятного простого числа в 2048-битном DSA, сгенерированного с помощью OpenSSL (используется openssl pkeyparam -textдля извлечения шестнадцатеричной строки) с использованием PARI isprime(APR-CL, как указано): около 80 с на быстром ноутбуке. Для справки, Chromium нужно чуть более 0,25 с для каждой итерации моей демонстрационной реализации JavaScript теста Фробениуса (которая намного сильнее, чем MR), поэтому APR-CL, безусловно, параноидален, но выполним.
Арне Фогель
2

O(f(n))O(f(n))O(g(n))nnn

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

ВЗН
источник
АКС более эффективен, чем что? Какой конкурс?
Yuval Filmus
все остальные алгоритмы. в основном вероятностный? подробности в газете
взн