Самыми быстрыми методами проверки для этого размера будут APR-CL (например, mpz_aprcl ) и ECPP (например, Primo или ecpp-dj ).APR-CL является детерминированным и почти полиномиальным временем, в то время как ECPP рандомизирован, но возвращенный ответ доказан, а не вероятностен.В качестве альтернативы, используйте конструктивный метод для проверенных простых чисел, таких как методы Маурера или Шоу-Тейлора.Это методы для быстрой генерации случайных n-битных простых чисел, созданных путем построения доказательств в стиле Поклингтона.С практической точки зрения, если вы генерируете случайных кандидатов, а не получаете их от третьей стороны, то показатели ошибок по Миллеру-Рабину чрезвычайно низки, и почти все люди в этом случае удовлетворены несколькими тестами Миллера-Рабина, использующимислучайные базы, возможно, с сильным тестом Лукаса в дополнение.См. FIPS 186-4 для большого количества информации о конструктивных методах и рекомендациях для возможного простого тестирования.
Времена показаны в этом графике для выбора случайных n-значных простых чисел, проходящих пробное деление, BPSW (эффективное вероятное простое испытание), две версии AKS, APR-CL и ECPP.Это показывает, как AKS сравнивается с другими методами.
Я не добавил детерминированный MR, так как полагаю, что вы не говорите о 64-битных входах, и вам нужно либо протестировать n / 4 базы, либодокажите гипотезу Римана, так что вам нужно только проверить 2 * log ^ 2 (n) баз.Ни один из них не является привлекательным по сравнению с другими нашими вариантами, даже если вы используете последний без доказательства.На практике версия Bach быстрее, чем AKS, как и ожидалось, но заметно медленнее, чем ECPP и APR-CL в моих тестах с C + GMP.Я не смотрел на асимптотику, но при 300 цифрах он более чем в 100 раз медленнее.Следовательно, я не вижу никакой точки зрения по сравнению с APR-CL (Det MR медленнее) или ECPP (Det MR медленнее и ECPP дает вам сертификат для загрузки).
Документ Брента можно найти в этом версия UMS10 от 2010 , а также аналогичная версия от 2006 .Это в основном согласуется с тем, что я нашел в более современных реализациях C + GMP различных алгоритмов.AKS является знаковым теоретическим результатом, но в настоящее время не имеет практического применения.