Построение больших простых чисел с использованием полного разложения на простые множители
Хорошо известен следующий результат :

Теорема 5.  Пусть  -- нечетное натуральное число, , и -- известное разложение на простые множители . Если для каждого существует натуральное число такое, что 
   и 
то  -- простое число. 
На этой теореме основан следующий метод Миллера построения больших простых чисел. Для некоторого набора известных простых чисел и показателей вычисляем . С помощью некоторого вероятностного теста (см. раздел 13.2) проверяем, не является ли составным. Если нет, т. е. вероятно простое, то генерируем случайную последовательность натуральных чисел из интервала . Для каждого вычисляем и для всех таких, что при всех . Если для некоторого , то составное. В противном случае мы докажем, что простое, когда для всех найдем такое, что . 
В работе Плейстеда  указан способ правильной организации вычислений для проверки сравнений указанного метода. А именно, следует положить , , , . Сначала следует вычислить , затем , . 
Наконец, нужно вычислить: 
	для	   	

и
	
	для	   	

делая это рекурсивно тем же методом. Мы также при этом найдем , возведя в квадрат , так как . При вычислениях этим способом требуется умножений по модулю . 
Зададимся теперь вопросом: какой из вероятностных тестов и сколько раз применять? Рекомендуется тест Миллера -- Рабина . Поскольку на отрезке доля простых чисел составляет примерно , то надо применить тест раз, где определяется из неравенства . Тогда вероятность того, что составное, будет меньше вероятности того, что простое (это эвристическое рассуждение). 
Подытоживая сказанное, простоту такого, что , проверяем с помощью следующего алгоритма. 
    1. Тестируем на простоту методом Миллера -- Рабина раз, где определяется из неравенства . 
    2. Если не оказалось, что составное, то перебираем несколько значений и для них проверяем условия метода Миллера. Обычно перебирают 4-6 значений . 
    3. Если до сих пор не обнаружено, что составное и не доказано, что простое, то далее чередуют: для одного тест Миллера -- Рабина, для трех метод Миллера и т. д. до тех пор, пока не докажут, что простое или составное. 
Эвристическая оценка сложности проверки простоты чисел , не превосходящих некоторой границы , с помощью этого метода составляет арифметических операций по модулю чисел, не превосходящих . 
Таким образом, для построения больших простых чисел нам остается лишь определить, как выбирать набор , т. е. какое взять . Для этого предложен ряд стратегий.