Я пишу реализацию криптографического протокола. До сих пор мне было трудно найти самый быстрый детерминированный тест примитивности для 1024-битных до 4096-битных целых чисел (от 308 до 1233 цифр). Я знаю несколько вариантов, но мне не удалось найти сравнения скорости в реальном мире.
В частности, как выполняется тест AKS по сравнению с детерминированной версией теста Рабина-Миллера и теста на проверку правильности эллиптической кривизны (и других) для общих случайных чисел такого размера?
Эта статья отвечает на ваш вопрос:
ПРЕИМУЩЕСТВА ИСТОЧНИКА Ричарда П. Брент: http://cs.anu.edu.au/student/comp4600/lectures/comp4600_primality.pdf
Он сравнивает по сложности и "реальной скорости" 3 алгоритма.
Я новичок, поэтому я не могу прокомментировать указанную выше ссылку, но вот ссылка интернет-архива на эту статью:
Наиболее быстрыми методами доказательства такого размера будут APR-CL (например, mpz_aprcl) и ECPP (например Primo или ecpp-dj). APR-CL является детерминированным и почти полиномиальным временем, в то время как ECPP рандомизирован, но возвращаемый ответ доказан, а не вероятностен. Альтернативно, используйте конструктивный метод для доказанных простых чисел, таких как методы Маурера или Шау-Тейлор. Это методы быстрого генерации случайных n-битовых простых чисел, созданных путем создания доказательств в стиле Поклинтона. С практической точки зрения, если вы генерируете случайных кандидатов, а не получаете их от третьего лица, тогда коэффициенты ошибок для Миллера-Рабина необычайно низки, и почти все люди в этом случае удовлетворяются несколькими испытаниями Миллера-Рабина, используя случайные базы, возможно, с сильным тестом Лукаса. См. FIPS 186-4 для получения подробной информации о конструктивных методах и рекомендациях для вероятного простого тестирования.
Времена показаны в этот график для выбора случайных n-значных простых чисел, проходящих через пробное деление, BPSW (эффективный вероятный простой тест), две версии AKS, APR-CL и ECPP. Это показывает, как AKS сравнивается с другими методами.
Я не добавлял детерминированный МР, поскольку я предполагаю, что вы не говорите о 64-битных входах, и над тем, что вам нужно либо проверить n/4 базы, либо доказать гипотезу Римана, так что вам нужно только проверить 2 * log ^ 2 (n). Ни один из них не привлекателен по сравнению с нашими другими вариантами, даже если вы используете последний без доказательства. На практике версия Bach быстрее, чем AKS, как ожидалось, но заметно медленнее, чем ECPP и APR-CL в моих тестах с C + GMP. Я не рассматривал асимптотики, но на 300 цифр он более чем на 100 раз медленнее. Следовательно, я не вижу никакой точки против APR-CL (Det M-R медленнее) или ECPP (Det M-R медленнее, и ECPP дает вам сертификат для загрузки).
Бумагу Brent можно найти в этой версии UMS10 с 2010 года, а также аналогичная версия с 2006 года. Это в основном согласуется с тем, что я нашел из более современных реализаций в C + GMP различных алгоритмов. AKS - знаковый теоретический результат, но он не имеет практического применения.