194 Глава 16. ВЫБОР ПАРАМЕТРОВ КРИПТОСИСТЕМЫ RSA

6. Строим p - ближайшее простое число, сравнимое с нечетным числом p0

по модулю rs, т.е. тестируем на простоту числа вида p = p0 + 2krs , k=0, 1, …,

пока не найдется простое число (либо сработают ограничения реализации).

Алгоритм основан на следующей теореме.

Теорема (Гордон). Если r, s - нечетные простые числа, то простое число p

удовлетворяет условиям p = −1(mod s), p =1(modr), тогда и только тогда,

когда оно представимо в виде		p = p0 + 2krs , где		p0 - нечетное число из пары,
u,u + rs .
Действительно,	пусть	p = p0 + 2krs ,		тогда p =u = −1(mod s),
p =u =1(modr) и p - искомое простое число.
Покажем, что простое число p′, не представимое в виде						p = p + 2krs ,
						0
не удовлетворяет условию теоремы.
Действительно, предположим обратное. По условию,					p′= −1(mod s),
p′=1(modr), т.е.	p′= p(mod s),		p′ = p(modr). Поэтому			p′− p делится
на rs и, естественно, на двойку,			т.е. p′ = p(mod 2rs)= p			(mod 2rs), что
				0

противоречит допущению.

16.3. Пример построения сильно простого числа

1. Строим исходное случайное простое число s размером, скажем, в 6 битов. Выбираем псевдослучайно шестибитовое число: x = 46. В промежутке

[46,46 +5]определяем простое число s = 47.

2. Строим случайное простое число t, аналогично построению числа s.

Пусть x = 25. В промежутке [25,25 + 4]определяем простое число t = 29.

3. Строим простое число r =1+ 2lt , перебирая l в промежутке [1,4].

Получаем r = 59.

Метод Гордона построения сильно простых чисел 195

4. Вычисляем u(r,s), решая с помощью китайской теоремы об остатках систему: u =1(r), u = −1(s).

Используя расширенный алгоритм Эвклида, получим соотношение

4 59 −5 47 =1, откуда: 59−1 mod 47 = 4, 47−1 mod59 = −5 .

Следовательно,

u(r,s)=1 47 (47−1 mod59)+ (−1) 59 (59−1 mod 47)= −471= 2302(2773).

5.	Число u(r,s) - четное, поэтому полагаем p0 = 2302 +59 47 =5075 .
6.	Строим простое число, сравнимое с p0	по модулю 2773, тестируя на
простоту числа вида p = p0 + 2 2773k .		При k = 0,1,2,3 получаем

соответственно: 5075, 10621, 11167, 21713. Лишь последнее число является простым.