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