13.6 Полиномиальные алгоритмы доказательства простоты с помощью известного полного разложения на простые множители

В работе Конягина и Померанса [KonP] был предложен ряд алгоритмов, позволяющих детерминированно доказывать, что  -- простое или составное число, с полиномиальной сложностью, если известно полное или частичное разложение на простые множители.

Справедлива, например, следующая теорема.

Если известно полное разложение на простые множители, то имеется алгоритм, который доказывает, что  -- простое или составное число, за арифметических операций.

Подобные алгоритмы были известны и ранее, но константа в показателе в оценке сложности была хуже.

Практическое применение этих алгоритмов при построении больших простых чисел может быть таким. Допустим, что мы выбрали с известным разложением на простые множители; кроме того, оказалось, что вероятно простое (по методу Миллера -- Рабина из раздела 13.2), но нам не удается доказать простоту методом Миллера. Тогда можно применить один из алгоритмов Конягина -- Померанса для доказательства простоты .