Алгоритмы проверки простоты чисел

Введение

Алгоритм определения, является ли число простым. Тест на простоту — это алгоритм для определения, является ли заданное число простым. Он используется в различных областях математики, в том числе в криптографии. В отличие от разложения на множители, тесты на простоту обычно не выдают простые множители, а лишь указывают, является ли заданное число простым или составным. Разложение на множители считается вычислительно сложной задачей, в то время как проверка на простоту относительно проста (время её работы полиномиально зависит от размера входных данных). Некоторые тесты на простоту доказывают, что число является простым, а другие, такие как тест Миллера — Рабина, доказывают, что число составное. Поэтому последние, возможно, точнее называть тестами на составность, а не тестами на простоту.

Другие испытания

Леонард Адлеман и Минг Де Хуан представили безупречный (но с ожидаемым полиномиальным временем работы) вариант теста простоты на основе эллиптических кривых. В отличие от других вероятностных тестов, этот алгоритм генерирует сертификат простоты, и, следовательно, может быть использован для доказательства того, что число является простым. На практике алгоритм является неприемлемо медленным. Если бы квантовые компьютеры были доступны, проверка простоты могла бы выполняться асимптотически быстрее, чем на классических компьютерах. Комбинация алгоритма Шора, метода факторизации целых чисел, и теста простоты Поклинтона могла бы решить задачу за .

Быстрые детерминированные тесты

В начале XX века было показано, что следствие малой теоремы Ферма может быть использовано для проверки на простоту. Это привело к созданию поклингтонского теста простоты. Однако, поскольку этот тест требует частичной факторизации n − 1, время выполнения в худшем случае оставалось довольно медленным. Первым детерминированным тестом простоты, значительно более быстрым, чем наивные методы, был тест циклотомии; его время выполнения может быть доказано как O((log n)c log log log n), где n — число, которое необходимо проверить на простоту, а c — константа, не зависящая от n. Было сделано множество дальнейших улучшений, но ни одно из них не удалось доказать как имеющее полиномиальное время выполнения. (Время выполнения измеряется в терминах размера входных данных, который в данном случае составляет ~ log n, то есть количество бит, необходимых для представления числа n.) Можно доказать, что тест простоты на основе эллиптических кривых работает за время O((log n)6), если верны некоторые предположения из аналитической теории чисел. Аналогично, при обобщённой гипотезе Римана можно доказать, что детерминированный тест Миллера, лежащий в основе вероятностного теста Миллера — Рабина, работает за время Õ((log n)4). На практике этот алгоритм медленнее двух других для размеров чисел, с которыми вообще можно работать. Поскольку реализация этих двух методов довольно сложна и создаёт риск ошибок программирования, часто предпочтение отдаётся более медленным, но более простым тестам. В 2002 году Маниндра Агравал, Нирадж Кайал и Нитин Саксена изобрели первый доказуемо безусловный детерминированный тест простоты за полиномиальное время. Тест простоты AKS работает за время Õ((log n)12) (улучшенный до Õ((log n)7.5) в опубликованной редакции их работы), которое можно дополнительно сократить до Õ((log n)6), если верна гипотеза Софи Жермен. Впоследствии Ленстра и Померанс представили версию теста, которая работает за время Õ((log n)6) безусловно. Агравал, Кайал и Саксена предлагают вариант своего алгоритма, который будет работать за время Õ((log n)3), если верна гипотеза Агравала; однако, эвристический аргумент Хендрика Ленстры и Карла Померанса предполагает, что она, вероятно, неверна, но всё же может быть верной.

Near the beginning of the 20th century, it was shown that a corollary of Fermat's little theorem could be used to test for primality. This resulted in the Pocklington primality test. However, as this test requires a partial factorization of n − 1 the running time was still quite slow in the worst case. The first deterministic primality test significantly faster than the naive methods was the cyclotomy test; its runtime can be proven to be O((log n)c log log log n), where n is the number to test for primality and c is a constant independent of n. Many further improvements were made, but none could be proven to have polynomial running time. (Running time is measured in terms of the size of the input, which in this case is ~ log n, that being the number of bits needed to represent the number n.) The elliptic curve primality test can be proven to run in O((log n)6), if some conjectures on analytic number theory are true. Similarly, under the generalized Riemann hypothesis, the deterministic Miller's test, which forms the basis of the probabilistic Miller–Rabin test, can be proved to run in Õ((log n)4). In practice, this algorithm is slower than the other two for sizes of numbers that can be dealt with at all. Because the implementation of these two methods is rather difficult and creates a risk of programming errors, slower but simpler tests are often preferred. In 2002, the first provably unconditional deterministic polynomial time test for primality was invented by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. The AKS primality test runs in Õ((log n)12) (improved to Õ((log n)7.5) in the published revision of their paper), which can be further reduced to Õ((log n)6) if the Sophie Germain conjecture is true. Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log n)6) unconditionally. Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in Õ((log n)3) if Agrawal's conjecture is true; however, a heuristic argument by Hendrik Lenstra and Carl Pomerance suggests that it is probably false. may still be true.

Сложность

В теории вычислительной сложности формальный язык, соответствующий простым числам, обозначается как PRIMES. Легко показать, что PRIMES находится в Co NP: его дополнение COMPOSITES находится в NP, поскольку можно определить составность, недетерминированно угадывая делитель. В 1975 году Воган Пратт показал, что существует сертификат простоты, который можно проверить за полиномиальное время, и, таким образом, что PRIMES находится в NP, и, следовательно, в \mathsf{NP \cap coNP}. Подробности см. в статье «Сертификат простоты». Последующее открытие алгоритмов Соловая-Штрассена и Миллера-Рабина поместило PRIMES в coRP. В 1992 году алгоритм Адлемана — Хуанга

Теоретические методы

Существуют определенные методы теории чисел для проверки, является ли число простым, такие как тест Лукаса и тест Прота. Эти тесты обычно требуют факторизации n + 1, n − 1 или аналогичной величины, что означает, что они не подходят для общей проверки простоты, но часто оказываются весьма эффективными, когда известно, что проверяемое число n имеет специальный вид. Тест Лукаса основан на том факте, что мультипликативный порядок числа a по модулю n равен n − 1 для простого n, если a является примитивным корнем по модулю n. Если мы можем доказать, что a является примитивным корнем для n, мы можем доказать, что n является простым.