Вперед: 13.7.3 Всегда ли результатом работы Алгоритма являются простые числа?
Вверх: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма"
Назад: 13.7.1 Общетеоретические обоснования
  Содержание
  Предметный указатель
13.7.2 Алгоритм
В основу используемого в Стандарте алгоритма
построения больших простых чисел положена следующая
теорема (отметим, что в Стандарте отсутствуют ссылки
на какую-нибудь научную литературу, что создает
определенные трудности при анализе).
Теорема 8.
Пусть ,
, где
-- нечетное простое число, -- натуральное число,
взаимно простое с , и
Тогда, если
то -- простое число.
В Алгоритме эта теорема используется при .
Алгоритм строит последовательность простых чисел
длины
соответственно, причем
,
, . При этом
построение начинается с и для
число строится по в виде
и число всякий раз подбирается так, чтобы при
были выполнены условия теоремы 8. Простые числа
и имеют все необходимые свойства. Дадим
теперь формальное описание Алгоритма. При этом мы
опускаем построение последовательности случайных чисел
, равномерно распределенной на интервале . Для
наших целей это построение не принципиально.
Алгоритм построения простых чисел и
,
,
имеющих длину соответственно и битов:
1.
Вычислить последовательность чисел
по правилу:
;
если
, то
;
если , то .
2.
Найти наименьшее простое число длины
битов.
3.
.
4.
Вычислить случайное число на интервале
и положить
(Здесь и
обозначают целую часть числа
и наименьшее целое, не меньшее, чем .) Если
нечетно, положить
.
5.
.
6.
Вычислить
.
7.
Если
, то перейти к шагу 4.
8.
Проверить условия
Если хотя бы одно из условий не выполнено, то положить
, и перейти к шагу 6. Если выполнены оба
условия, то положить
.
9.
Если
, то перейти к шагу 4. Если же
, то и -- искомые простые числа.
Вперед: 13.7.3 Всегда ли результатом работы Алгоритма являются простые числа?
Вверх: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма"
Назад: 13.7.1 Общетеоретические обоснования
  Содержание
  Предметный указатель
|