Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма"
В указанном Стандарте предлагается алгоритм построения простых чисел длины битов, , с простым делителем длины битов, , числа . При этом частное также имеет большой простой делитель длины 512 битов. Наличие достаточно больших простых делителей у числа вызвано требованиями предлагаемого Стандартом алгоритма электронной цифровой подписи. Алгоритм построения чисел с указанными свойствами предлагается в двух модификациях (Процедуры В и В), ориентированных соответственно на 16- и 32-битовые вычислительные машины. Модификации отличаются лишь размерами случайных чисел, вырабатываемых случайными датчиками, основанными на линейном конгруэнтном методе и указанными в Стандарте. В Процедуре В такой датчик имеет вид 

а в процедуре В 

Основу указанных процедур составляют соответственно Процедуры А и А, позволяющие строить при каждом целом простые числа длины битов с простым делителем длины битов (здесь  -- целая часть числа). Процедуры А и А также отличаются лишь размерами используемых случайных чисел. Мы опишем и затем проанализируем алгоритм, лежащий в основе этих процедур, на примере процедуры А. Использование этого алгоритма в процедурах В и В не имеет принципиальных отличий.
Общетеоретические обоснования
Основную часть алгоритма можно описать следующим образом. Предположим, что как-то удалось построить простое число и требуется построить еще большее простое число . Это большее число ищется в виде 
	(1)	

Можно, выбирая как-либо целые числа , тестировать появляющиеся числа на простоту, например, с помощью тестов, использующих знание частичного разложения на множители (см. раздел. 13.5). Для этого нужно, чтобы число , разложение которого на простые множители, вообще говоря, считается неизвестным, было не очень большим по сравнению с , скажем , где возрастающая не очень быстро функция описывается в соответствующем тесте. Конструкция , естественно, должна быть не уникальной, а обеспечивать получение достаточно большого количества простых чисел в прогрессии . Это достигается случайным выбором начала отсчета -- четного числа на промежутке , перебором чисел и последующим тестированием на простоту. Мы сейчас коротко обсудим теоретические основы такого метода построения простых чисел. 
Прежде всего, согласно теореме Дирихле, доказанной еще в 1839 г., прогрессия (1) содержит бесконечное количество простых чисел. Нас интересуют простые числа, лежащие недалеко от начала прогрессии, ведь согласно условиям тестирования должно выполняться ограничение . Оценка наименьшего простого числа в арифметической прогрессии была получена еще в 1944 г. Ю. В. Линником. Она утверждает, что существует абсолютная постоянная такая, что наименьшее простое число в прогрессии (1) не превосходит . Постоянная очень велика, заведомо выполняется неравенство . В предположении расширенной гипотезы Римана о нулях L-функций Дирихле можно доказать (см. [Прах], с. 272), что при любом наименьшее простое число в прогрессии (1) не превосходит . Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа (1) с не существует. Тем не менее опыт вычислений на ЭВМ показывает, что простые числа в прогрессии встречаются достаточно близко к ее началу. Упомянем в этой связи гипотезу о существовании бесконечного количества простых чисел с условием, что число также простое (уже первый член прогрессии (1) есть простое число). 
Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии. Ведь если это расстояние велико, нет надежды обеспечить построение большого количества простых . Перебор чисел до того момента, как мы наткнемся на простое , окажется слишком долгим. В более простом вопросе о расстоянии между соседними простыми числами и в натуральном ряде доказано лишь, что , что, конечно же, слишком велико для наших целей. Вместе с тем, существует так называемая гипотеза Крамера (1936 г.), что , дающая вполне приемлемую оценку. Вычисления на ЭВМ показывают, что простые числа в арифметических прогрессиях расположены достаточно плотно. 
В качестве итога обсуждения в этом пункте подчеркнем следующее: если принять на веру, что наименьшее простое число, а также расстояние между соседними простыми числами при в арифметической прогрессии (1) оцениваются величиной , то предложенная схема построения простых чисел имеет полиномиальную сложность. Кроме того, несмотря на отсутствие теоретических оценок времени работы алгоритмов, отыскивающих простые числа в арифметических прогрессиях со сравнительно большой разностью, на практике эти алгоритмы работают вполне удовлетворительно. 
Алгоритм
В основу используемого в Стандарте алгоритма построения больших простых чисел положена следующая теорема (отметим, что в Стандарте отсутствуют ссылки на какую-нибудь научную литературу, что создает определенные трудности при анализе). 
Теорема 8.  Пусть , , где  -- нечетное простое число,  -- натуральное число, взаимно простое с , и 
		(2)	
		(3)	

Тогда, если то  -- простое число. 
В Алгоритме эта теорема используется при . 
Алгоритм строит последовательность простых чисел 

длины соответственно, причем , , . При этом построение начинается с и для число строится по в виде 

и число всякий раз подбирается так, чтобы при были выполнены условия теоремы 8. Простые числа и имеют все необходимые свойства. Дадим теперь формальное описание Алгоритма. При этом мы опускаем построение последовательности случайных чисел , равномерно распределенной на интервале . Для наших целей это построение не принципиально. 

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

(Здесь и обозначают целую часть числа и наименьшее целое, не меньшее, чем .) Если нечетно, положить . 
    5. . 
    6. Вычислить . 
    7. Если , то перейти к шагу 4. 
    8. Проверить условия 

Если хотя бы одно из условий не выполнено, то положить , и перейти к шагу 6. Если выполнены оба условия, то положить . 
    9. Если , то перейти к шагу 4. Если же , то и  -- искомые простые числа.
Всегда ли результатом работы Алгоритма являются простые числа?
Указанный алгоритм, вообще говоря, может выдавать в качестве и составные числа. 
Выбор , указанный в пункте 4, и пункт 7 Алгоритма обеспечивают выполнение неравенств 
	(4)	

означающих в силу нечетности , что длина в точности равняется битов. Кроме того, если четно, то и из (4) следует 

т. е. выполнены условия первого пункта теоремы 8 и можно утверждать, что  -- простое число. 
Если же нечетно, то и 

При , близком к своему наименьшему возможному значению , возможные для значения, близкие к , будут примерно равны , т. е. . Это означает, что параметры будут находиться вне пределов справедливости теоремы 8 и, следовательно, гарантировать простоту числа в таком случае нельзя. 
Если исходное значение , скажем, 256 или 512, то все числа четны и все на основании теоремы 8 просты. Но, если, например, , все числа нечетны и тогда на каждом шаге Алгоритма нельзя гарантировать простоту и, следовательно, простоту и . Но именно 255 указывается в процедуре В как допустимое значение длины числа , используемого в алгоритме цифровой подписи. 
Указанную неточность в Алгоритме можно исправить несколькими способами. 

а) Можно было бы определить последовательность в шаге 1 Алгоритма равенствами . Тогда при любом выполняется неравенство и из (4) следует 

Это в силу теоремы 8 позволяет утверждать, что  -- простое число. При этом битовая длина числа , получаемого в результате работы Алгоритма, будет равна . При нечетных оно будет длиннее на 1 бит. 
Если равно , такое изменение Алгоритма не приведет к увеличению числа итераций. Не изменится число итераций и для . А вот для изменение Алгоритма приведет к увеличению числа итераций на 1. 
б) Увеличение диапазона для в теореме 8 позволяет при заданном строить простые числа, имеющие большую величину. Однако условие в формулировке теоремы ослабить нельзя. Так, возможен случай, когда для составного выполнены условия (2) и (3). Например, этот случай имеет место 
    1) при , , ; 
    2) при , , ; 
    3) при , , ; 
    4) при , , ; 
    5) при , , . 

В следующей теореме описываются исключительные случаи, которые могут возникать при увеличении интервала возможных значений до . 
Теорема 9.  Пусть , , где  -- нечетное простое число,  -- натуральное число, взаимно простое с , и 

Тогда если , то  -- простое число или , где  -- простое число. В последнем случае также выполняется сравнение 
	(5)	

Следствие.  Если выполнены условия теоремы 9 и , , то  -- простое число. 
Нам не известны простые числа , удовлетворяющие одновременно двум условиям 
 		(6)	
 	-- простое число	(7)	

Среди простых чисел имеется лишь два числа 1093 и 3511, удовлетворяющих условию (6). Условие (7) для них, конечно же, нарушается. Тем не менее мы не должны исключать возможность составного числа при , хотя эта возможность и маловероятна. 
Изменим пункт 8 Алгоритма, добавив в него проверку условия . 
Так как при любом справедливо неравенство , то при выполнении условий пункта  8 Алгоритма будем иметь 

Это означает выполнимость всех условий следствия из теоремы 9. Но тогда можно утверждать простоту числа .Распознает ли Алгоритм все простые числа?
Основное время в процессе работы Алгоритма уходит на поиск простых чисел в прогрессии . Если Алгоритм наткнулся на такое число, то проверка простоты его, в случае справедливости условий теоремы 8, выполняется сравнительно быстро. Поэтому важным качеством алгоритма должна быть способность доказывать простоту каждого простого числа, встречающегося в прогрессии. 
Отметим, в этой связи, что не все простые числа могут быть распознаны указанным алгоритмом. Другими словами, перебирая последовательно четные числа , и проверяя числа на простоту, Алгоритм может не распознать некоторые простые числа и, увеличив значение , продолжать работу дальше. Это, конечно, может приводить к увеличению времени работы алгоритма. Укажем некоторые примеры чисел , не идентифицируемых Алгоритмом как простые. Простыми являются все числа из следующего списка: 
    1) , , ; 
    2) , , ; 
    3) , , ; 
    4) , , ; 
    5) , , . 
Во всех указанных случаях и имеют место сравнения 

Значит, если одно из указанных чисел встретится в Алгоритме как , а соответствующие значения будут равны , то числа не будут приняты как простые и Алгоритм продолжит работу. 
Указанные примеры являются частными реализациями при следующего общего утверждения. 
Предложение 1.  Пусть  -- простое число, причем простое и . Если , , и порядок числа по модулю не превосходит , то и, следовательно, простое число не удовлетворяет условиям теоремы 8. 
Исключить указанный пропуск простых чисел можно за счет проверки в Алгоритме условий теоремы 8 не только при , но и при других значениях основания . 
Предложение 2.  Для каждого простого числа , , , на промежутке имеется не менее чисел , для которых выполнены условия теоремы 8. 
Предложение 2 показывает, что, выбирая случайным образом числа на промежутке при простом , можно с вероятностью, большей чем , найти число , для которого будут выполнены условия теоремы 8. 
Удобнее, однако, выбирать числа последовательно: . Увеличение продолжительности работы при этом произойдет лишь для тех простых чисел , которые пропускались Алгоритмом. Но и для них, если принять на веру, что корни сравнения распределены равномерно на промежутке , необходимое для выполнимости теоремы 8 число будет найдено, согласно предложению 2, достаточно быстро. 
Но как будет работать измененный алгоритм, если число составное? Существуют составные числа (числа Кармайкла) для которых условие (2) выполняется при любом , , так же как и для простых чисел. Эти числа встречаются достаточно редко. Тем не менее в 1993 г. доказано, что их бесконечно много. Известна модификация теста теоремы 8, основанная на следующей теореме: 
Теорема 10 Пусть M -- нечетное составное число, , нечетно, и  -- множество натуральных чисел , , для которых выполнены условия: 
    1) , 
    2) при всех , 

Тогда количество элементов в не меньше . 
Если  -- простое число, то для каждого , , согласно малой теореме Ферма имеем 

т. е. для простого хотя бы одно из условий теоремы 10 обязательно нарушается. В то же время, как следует из теоремы 9, для составного числа нарушение хотя бы одного из условий теоремы 9 происходит с вероятностью при случайном выборе на интервале . При этом, что легко видеть, выполняется сравнение (2). Таким образом, если проверять для числа выполнимость условий 1) и 2) для случайно выбранных значений , или, что технически удобнее, для , то с вероятностью, большей, чем , составное число будет при этом опознано как составное. 
Итак, изменим пункт 8 Алгоритма следующим образом: 
  8.1. Положить . Вычислить целое и нечетное число такие, что ( . 
  8.2. Положить . 
  8.3. Проверить условие 

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

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

Если это условие не выполняется, перейти в пункт 8.2. 
  8.7. Проверить условие . Если это условие не выполняется, перейти в пункт 8.2. 
  8.8. Положить . 
Как уже было сказано, приведенное выше изменение пункта 8 Алгоритма позволит достаточно быстро доказывать как простоту числа , если оно простое, так и непростоту, если оно составное. При простом Алгоритм из пунктов 8.3 и 8.4 будет всегда переходить в пункт 8.6, и согласно предложению 2 довольно быстро будет найдено число , для которого выполнится условие (8). Условие пункта 8.7 для простого числа , конечно же, будет выполнено. Так что Алгоритм попадет в пункт 8.8, а затем перейдет к построению простого числа . Если же число составное и нарушается хотя бы одно из условий пунктов 8.3 и 8.4, то согласно следствию из теоремы 9 для не могут выполняться оба условия пунктов 8.6 и 8.7. Но тогда Алгоритм перейдет в пункт 8.2, будет вычислено новое значение , с которым будут проверяться условия пунктов 8.3 и 8.4. Согласно теореме 10 довольно быстро будет обнаружено число , для которого будут выполнены условия пунктов 8.3 и 8.4. Тогда число будет определено как составное и из пункта 8.6 Алгоритм перейдет к построению нового числа . 
Отсеивание составных чисел
Можно добиться существенного сокращения времени работы Алгоритма, если предусмотреть в нем специальные приемы обработки составных чисел. 
Составные числа вида отсеиваются в Алгоритме с помощью теста теоремы 8. Но для большинства из них непростоту можно доказать значительно быстрее. Так каждое третье число в прогрессии делится на 3, каждое пятое делится на 5 и т. д. Пользуясь регулярностью расположения этих чисел, их можно вообще не рассматривать, перескакивая через них при выборе нового значения u в шаге 8 Алгоритма. Это просеивание можно проделать следующим способом. 
Определив в пункте 4 Алгоритма очередное четное число , составим таблицу всех чисел из промежутка с условием, что и 15 взаимно просты. Это очень просто сделать, заставив пробегать все числа и вычисляя наибольший общий делитель 15 и . Вычисления можно еще упростить, если предварительно вычислить остатки от деления на 15 чисел и . Эта таблица чисел будет состоять из 8 чисел . Положим также 

Вместо одной переменной в Алгоритме нужно рассматривать две переменные и , положив в шаге 5 , , а затем вычисляя в шаге 8 

Легко видеть, что все числа прогрессии , , делящиеся на 3 или 5, будут при этом пропущены. 
Можно расширить количество маленьких делителей, добавив к множеству число и т. д. При этом доля остающихся в результате просеивания чисел будет равна соответственно 
   и т. д. 
Отметим, что длина таблицы остатков будет при этом равна , т. е. будет довольно быстро увеличиваться. 
Иной вариант организации просеивания, не использующий много памяти, но требующий несколько большего объема вычислений, можно реализовать так. Будем использовать вместо одной переменной две переменные и , которые будут равны остаткам от деления числа на 3 и 5 соответственно. Для этого шаг 5 представим как три следующих шага: 
  5.1. Положить 

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

и перейти в шаг 5.2. 
Кроме того, приведенный выше пункт 8.5 Алгоритма нужно изменить следующим образом: 
  8.5. Перейти в пункт 5.3. 
Как и выше, можно увеличить множество простых делителей , добавив к ним числа и т. д. 
Описанные выше приемы просеивания, исключают из рассмотрения числа , имеющие маленькие простые делители. В качестве еще одного средства отсеивания составных чисел можно использовать следующие изменения в пункте 7: 
    7. Если , то перейти к шагу 4. В противном случае проверить делимость числа на все простые числа, не превосходящие некоторой границы . В случае делимости вычислить новое значение (перейти в пункт 5.3). 
Для реализации этого пункта нужно предварительно, скажем, в пункте 1 Алгоритма запасти таблицу всех простых чисел, не превосходящих . 
После указанных в этом параграфе изменений к тестам пункта 8 будут приходить только числа , все простые делители которых превосходят границу . 
Замечания
1. Думается, что однозначный выбор числа , как наименьшего простого числа длиной в битов, в пункте 3 Алгоритма значительно сужает множество выдаваемых Алгоритмом пар простых чисел и . Очень просто организовать какой-либо случайный выбор на интервале , что расширит множество возможных чисел примерно в 5714 раз. Например, можно, выбрав случайным образом целое число на этом интервале, тестировать на простоту следующие за ним целые числа, проверяя их делимость на все простые, не превосходящие , ведь . 
2. В процессе работы Алгоритма можно контролировать не длину битовой записи числа -- достаточно грубую характеристику, а саму величину числа. Новый алгоритм, будет выдавать простое число , лежащее между двумя заданными границами и простой делитель , удовлетворяющий неравенствам 

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

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

Пункты 5 и 6 остаются без изменений. 
В пункте 7 должно стоять неравенство . 
Остальные пункты Алгоритма остаются без изменений. 
Проверим по индукции, что в процессе работы нового алгоритма строятся простые числа 

удовлетворяющие неравенствам 
	(10)	

При это следует из пункта 2 нового алгоритма. Из новых пунктов 4, 6 и 7 следуют неравенства 

что доказывает (10). 
С помощью неравенств (10), определения последовательностей , и пункта 7 нового алгоритма находим 

Таким образом, если  -- простое число, то для , , выполнены условия теоремы 8 и можно утверждать, что число также простое. 
Если внести в Алгоритм изменения пункта 8.7, то в (9) можно несколько расширить интервал возможных значений чисел , положив 

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