Алгоритм построения простых чисел
Описываемый ниже алгоритм построения больших простых чисел является модификацией Алгоритма, учитывающей высказанные в этом разделе замечания. Для его работы требуется таблица всех нечетных простых чисел, меньших . Такая таблица легко может быть составлена, например, проверкой делимости на нечетные числа, не превосходящие 361 (ведь ). По заданным целым числам , и , , , предлагаемый алгоритм строит простые числа и с условиями: 
	(11)	

Например, для , , , получаются простые числа и , имеющие битовую длину соответственно и . 

Алгоритм
    1. Вычислить две последовательности чисел 

где число выбрано так, что . 
    2. Найти простое число , удовлетворяющее неравенствам . Это можно сделать, перебирая случайным образом нечетные числа на указанном промежутке и проверяя их делимость на все простые, меньшие . 
    3. 
    4. Вычислить случайное число на интервале и положить 

(Здесь [x] и обозначают целую часть числа и наименьшее целое, не меньшее, чем .) Если нечетно, положить . 
    5. (В этом пункте алгоритма отсеиваются числа , делящиеся на 3 или на 5.) 
  5.1. Положить и для , , , , , вычислить 

  5.2. Если для всех , , выполняется , перейти в пункт 6. 
  5.3. Положить 

и перейти в пункт 5.2. 
    6. Вычислить . 
    7. Если , то перейти к пункту 4. В противном случае проверить делимость числа на все простые числа, не превосходящие . В случае делимости на какое-нибудь из указанных чисел перейти в пункт 5.3. 
    8. Ниже в этом пункте реализованы тесты проверки на простоту, описанные в теоремах 9 и 10 из раздела 13.7). 
  8.1. Положить . Вычислить целое и нечетное число такие, что . 
  8.2. Положить . 
  8.3. Проверить условие 

Если это условие нарушается, перейти в пункт 8.6. 
  8.4. При каждом , , проверить условие 

Если оно нарушается хотя бы при одном , перейти в пункт 8.6. 
  8.5. Перейти в пункт 5.3. 
  8.6. Проверить условие 

Если это условие не выполняется, перейти в пункт 8.2. 
  8.7. Проверить условие 

Если это условие не выполняется, перейти в пункт 8.2. 
  8.8. Положить . 
    9. Если , то перейти к пункту 4. Если же , то и  -- искомые простые числа. 
Отметим, что простота числа обеспечивается теоремой 9 из раздела 13.7. По этой же теореме в силу неравенств 

простым будет и число . 
Вышеописанный алгоритм был запрограммирован на языке UBasic, в котором реализованы арифметические операции с целыми числами величиной до . Соответствующая программа была применена для построения двух таблиц простых чисел и соответствующих простых делителей , . В первой содержатся 20 простых чисел , длина записи которых равна 512 битов, а во второй -- 15 чисел с длиной записи 1024 битов. На составление первой таблицы персональный компьютер с процессором 80386/7 потратил 9 мин. 20 сек., а на составление второй -- 30 мин. машинного времени.