Полиномиальные алгоритмы доказательства простоты с помощью известного полного разложения на простые множители
В работе Конягина и Померанса  был предложен ряд алгоритмов, позволяющих детерминированно доказывать, что  -- простое или составное число, с полиномиальной сложностью, если известно полное или частичное разложение на простые множители. 
Справедлива, например, следующая теорема. 
Теорема 7.  Если известно полное разложение на простые множители, то имеется алгоритм, который доказывает, что  -- простое или составное число, за арифметических операций. 
Подобные алгоритмы были известны и ранее, но константа в показателе в оценке сложности была хуже. 
Практическое применение этих алгоритмов при построении больших простых чисел может быть таким. Допустим, что мы выбрали с известным разложением на простые множители; кроме того, оказалось, что вероятно простое (по методу Миллера -- Рабина, но нам не удается доказать простоту методом Миллера. Тогда можно применить один из алгоритмов Конягина -- Померанса для доказательства простоты .