08.04.09.Печать_edit

Пусть p = qN + 1, где q — нечетное простое число, N — четное число и p < (2q + 1)2. Число p является простым, если выполняются следующие два условия:

1)2 qN = 1 mod p и

2)2 N 1 mod p.

Доказательство

Пусть есть порядок числа 2 по модулю p и p имеет следующее канони-

ческое разложение: p p 1 p 2		... p h . Ввиду условия 1)					делит p 1, т. е.
1	2		h
| p 1. В силу условия 2)	не является делителем числа							p 1		. Отсюда сле-
								q
дует, что q | . Согласно	теореме		Эйлера		2 (p) = 1 mod p,				следовательно,
| (p) q | (p), где ( p) p 1 1 p 2 1... p h 1( p					1)( p	1) ... ( p 1).			Пусть q совпа-
	1	2	h	1	2	h

дает с простым множителем pi. Из такого допущения следует, что p = qn для некоторого натурального числа n. Однако по условию теоремы имеем p = qN + 1. Поскольку q > 1 не может делить число 1, то приходим к противо-

речию, из которого следует, что q должно делить число pi 1, по крайней ме-

ре, для некоторого одного из значений i {1, 2, …, h}.

Таким образом, существует некоторое натуральное n 2, такое что имеем pi 1 = qn и pi = qn + 1. Следовательно, при некотором натуральном m получим:

p = mpi = m(qn + 1) = qN + 1 m = q(N mn) + 1.

При некотором натуральном s 0 имеем m = qs + 1 и p = (qn + 1)(qs + 1).

Пусть p есть составное число, тогда s 2 (поскольку N и n — четные числа, а s = N – mn), из чего следует p (2q + 1)2. Это противоречит условию теоремы, следовательно, s = 0 и число p является простым.

Схема построения алгоритма описывается следующим образом. Пусть требуется сформировать простое число p длины t 17 бит. С этой целью

41

строится убывающий набор натуральных чисел t0, t1, …, ts, где t0 = t и ts < 17 бит, для которых выполняется условие ti = [ti 1/2]. Последовательно вырабатываются простые числа ps, ps 1, …, p0, причем длина числа pi равна значению ti для всех i = 1, …, s. Исходное простое значение ps формируется путем случайного выбора числа размером менее 17 бит и проверки на простоту методом пробного деления.

Генерация простого числа pi 1 по простому числу pi осуществляется с использованием формулы

pi 1 = pi N + 1,

где N — случайное четное число, такое что длина числа pi N + 1 равна значе-

нию ti. Число pi 1 считается полученным, если одновременно выполнены следующие два условия:

1)2 pi N = 1 mod pi 1;

2)2 N 1 mod pi 1.

Если хотя бы одно из условий не выполнено, то значение N увеличива-

ется на 2, вычисляется новое значение pi 1, которое снова проверяется на простоту по указанным двум условиям. Такая процедура выполняется до тех пор, пока не будет получено простое число pi 1.

2.3. Извлечение корней по модулю

2.3.1. Вычисление квадратных корней

Извлечение квадратного корня по модулю используется как базовый примитив в ряде криптосистем. При составном модуле эта операция выполняется следующим путем: 1) разложение модуля n на простые множители: n p1 1 p2 2 ... pz Z , 2) извлечение корня из заданного числа по каждому из про-

стых модулей p1, p2, …, pz, и 3) последующее восстановление корня по составному модулю с помощью китайской теоремы об остатках. Вычисление корней по простому модулю сводится к одной или нескольким операциям возведения в степень по модулю. Сложность процедуры извлечения корня

42

зависит от конкретного значения простого модуля. Наиболее простым является случай, когда модуль сравним с числом 3 по модулю 4: p ≡ 3 mod 4.

Следующими по возрастанию сложности являются случаи	p ≡ 5 mod 8 и
p ≡ 1 mod 8 (случаи p ≡ 3 mod 8 и p ≡ 7 mod 8 относятся	к случаю p ≡

≡ 3 mod 4). При p ≡ 1 mod 8 используется общий алгоритм вычисления корней, который реализует операцию извлечения квадратного корня по произвольному простому модулю. Рассмотрим процедуру извлечения корней для указанных трех случаев.

Случай p ≡ 3 mod 4

Пусть a является квадратичным вычетом и требуется найти число x, такое что x2 ≡ a mod p, где простое p удовлетворяет условию p ≡ 3 mod 4. Для

p 1

квадратичных вычетов имеет место сравнение a 2 1mod p. Умножая обе

p 1

части этого сравнения на a, получаем: a 2 a mod p. Поскольку p ≡ 3 mod 4,

		p 1			p 1
	степень		есть целое число, поэтому мы можем определить:	x a 4 mod p.
	4

Возведением значения x в квадрат легко показать, что оно есть квадратный корень из числа a по модулю p. Таким образом, для рассматриваемого случая извлечение корня второй степени сводится к операции возведения в степень

p 1 по модулю p:

4

p 1

a a 4 mod p .

Случай p ≡ 5 mod 8

Пусть a является квадратичным вычетом и требуется найти число x, такое что x2 ≡ a mod p, где простое p удовлетворяет условию p ≡ 5 mod 8

p 1

										1 mod p . По-
(рис.1). Для квадратичных вычетов имеет место сравнение a 2
скольку p ≡ 5 mod 8, то при некотором натуральном k имеем: p – 1											= (8k + 5) –
			p 1
				a2(2k 1)	1 mod p .
1 = = 4(2k + 1). Поэтому a 2						Из последнего					сравнения
	p 1						p 1
следует, что либо a 4 a2k 1				1 mod p	(1), либо	a 4 a2k 1				1 mod p (2).

43

Если имеет место первый случай, то, умножая обе части сравнения (1) на a,

	p 3		a2	p 3			p 3		p 3
										есть целое число, откуда
имеем: a 4				8		(a	8 )2 a mod p , где
									8

следует формула для вычисления квадратного корня

p 3

a a 8 mod p .

Если имеет место второй случай, то, умножая обе части сравнения (2) на – 1,

p 1

имеем: a 4 ( 1) 1 mod p . Теперь представим –1 mod p как b4k 2mod p , где b есть произвольный квадратичный невычет по модулю p. Действительно, для

p 1

8k 4

b

b4k 2 1mod p . Таким образом, мы по-

невычета b имеем: b 2

2

p 1

p 1

2k 1 есть нечетное число. Умножая

лучили a 4 b4k 2 1 mod p (3), где

4

p 3

p 3

p 1

обе части сравнения (3) на a, получаем a 4 b4k 2

a 4

b 2 a mod p , где по-

казатели степеней чисел a и b являются четными, поэтому мы можем опреде-

p 3 p 1

лить x a 8 b 4 mod p (где показатели степеней чисел a и b являются натуральными числами).

Возведением значения x в квадрат легко показать, что оно есть квадрат-

p 3

p 1

x2 a

ный корень из числа a по модулю p:

4

b 2 a mod p .

p 1

1 mod p для вычисления квадратного

Таким образом, для случая a 4

корня может быть использована следующая формула:

p 3 p 1

a a 8

b 4

mod p .

При использовании этой формулы предварительно следует найти квадратичный невычет b, что осуществляется случайным выбором числа b ≤ p – 1,

p 1

за которым следует проверка выполнимости условия b 2 mod p p 1. Поскольку вероятность того, что случайное число является невычетом, равна 50 %, то нахождение квадратичного невычета требует в среднем выполнения

44

двух попыток. Описанная выше процедура извлечения квадратных корней по простому модулю поясняется блок-схемой, приведенной на рис. 1.

Начало

Задать числа a и p,

где p 5 mod 8

Нет	a( p 1) / 2 mod p 1		Да
	Нет		Да
			a( p 1)/ 4 mod p 1
	Найти невычет b:		p 3
	p 1
	b 2 mod p p 1		a a 8 mod p
	p 3	p 1
	a a 8	b 4	mod p

Нет корней

a

Конец

Рис. 1. Схема алгоритма вычисления квадратного корня по простому модулю p (случай p ≡ 5 mod 8)

Случай произвольного простого модуля

Пусть a является квадратичным вычетом и требуется найти число x, такое что x2 ≡ a mod p, где p — произвольное простое число. В этом общем случае задача решается с использованием определенного расширения приемов, примененных в случае p ≡ 5 mod 8. Для произвольного p можно записать:

p – 1 = 2 t r,

где t ≥ 1 и r — нечетное число. Пусть для вычета a и любого невычета b справедливо сравнение

45

a S b Z 1 mod p,

(4)

где S — нечетное число, а Z — четное число или ноль. Тогда, умножая обе

части последнего сравнения на a, получаем a S +1b Z ≡ a mod p, следовательно, можно определить значение x = a (S +1)/2 b Z /2 mod p, которое является квадратным корнем из a (это доказывается простым возведением значения x в квадрат). Для того чтобы найти представление единицы в виде (4), восполь-

p 1 p 1

зуемся сравнением a 2 1 mod p, представив его в виде a 2 bZ 1 mod p , т. е.

в виде, аналогичном (4), где в общем случае S = (p – 1)/2 является четным и

Z = 0. Рассмотрим сравнение (4) с начальными значениями S = (p – 1)/2 и Z = 0, в котором осуществим ряд последовательных шагов одновременного деления обоих показателей степеней чисел a и b на два (на одном шаге выполняем две операции присваивания S S /2 и Z Z /2), пока не получим нечетное S. При этом перед некоторыми шагами деления к значению Z будем прибавлять число (p – 1)/2, что соответствует умножению левой части (4) на

p 1
b 2 1 mod p . Выполнение операции	Z Z ( p 1) / 2 будем осуществ-

лять, если перед выполнением шага деления или при достижении условия прекращения цикла деления имеет место a S b Z –1 mod p. Заметим, что если при исходных значениях S = (p – 1)/2 и Z = 0 значение S является нечетным, то мы сразу имеем условие прекращения процесса деления показателей степеней на два, поэтому выполняется ноль шагов деления. В противном случае

после первого	шага деления имеем либо a S b Z 1 mod p, либо a S b Z
–1 mod. Во	втором случае мы дополнительно выполняем операцию
Z Z ( p 1) / 2	перед выполнением следующего шага деления или перед вы-

			S 1 Z
числением корня a a 2 b 2						mod p (если уже достигнуто нечетное значение
S).

46

Начало

Инициализация: R a( p 1) / 2 mod p ;
		1
	S ( p 1) / 2 ;		R2 1; Z 0 .
	Вычисление: R1R2 mod p
p 1	Нет		Да
		= 1
Z Z ( p 1) / 2			Нет	Да
			S mod 2 = 0
Нет		Да
	S mod 2 = 0		Вычисление:
			S S / 2; Z Z / 2 ;
Вычисление:			R aS	mod p ;
			1
S (S 1) / 2 ;			R bZ mod p
			2
Z Z / 2 ;
x aS bZ mod p			Конец

Рис. 2. Схема алгоритма вычисления квадратного корня из вычета a по простому модулю p (общий случай)

Заметим, что на первом шаге деления осуществляется деление на два нулевого значения Z и только потом выполняется операция Z Z ( p 1) / 2 , поэтому если имеется ненулевое значение Z, то в его разложение двойка входит с показателем степени, превышающим показатель степени числа 2 в разложении S (после одного и того же шага деления показателей степени чисел S и Z). Следовательно, в момент достижения нечетного значения S число Z является четным. Описанная выше процедура извлечения квадратных корней по простому модулю поясняется блок-схемой, приведенной на рис. 2.

Извлечение корней по составному модулю

Если составной модуль n представляется в виде произведения первых степеней простых чисел: m = p1, p2, …, ps, то нахождение квадратных корней сводится к нахождению квадратных корней по модулю, равному каждому из множителей p1, p2, …, ps. Легко видеть, что число a ≠ 0, являющееся квадра-

47

тичным вычетом по составному модулю, является квадратичным вычетом по всем модулям p1, p2, …, ps: x2 a mod m x2 a mod p1, x2 a mod p2,

…, x2 a mod ps. Каждое из последних s сравнений имеет два решения: x1 и p1 – x1; x2 и p2 – x2; …, xs и ps – xs соответственно. Выбирая из каждой из этих пар по одному корню, можно составить 2s различных систем сравнений вида

					{x1, p x1},
x x1 mod p1, x1
			,		{x2 , p x2},
x x2 mod p2				x2
				. . . .
		mod ps ,			{xs , p xs}.
x xs				xs

Каждую из этих систем можно решить, используя китайскую теорему об остатках, в результате чего будет вычислено 2s различных корней

a mod m, значения которых не превышают m.

2.3.2. Извлечение корней степени n > 2 по простому модулю

Пусть число a является вычетом n-й степени по простому модулю p. Если НОД (n, p – 1) = 1, то имеется единственный корень, где z = r –1 mod p. Ес-

ли НОД (n, p – 1) = δ, то сравнение xn a mod p имеет δ решений. Если из-

вестно одно решение x0, то остальные решения сравнения xn a mod p (1) можно найти следующим путем:

Вычислить значения a aw mod p , где w / n mod p и перейти к рас-

смотрению сравнения x a mod p (2), которое равносильно (1). В частно-

сти, если x0 есть решение (1), то x0 является также и решением (2). (Решение x0 удобнее искать как решение сравнения (2), поскольку δ ≤ n.)

Поскольку δ | p – 1, то легко можно найти некоторое число g, относя-

щееся к δ по модулю p как к показателю. Числа в множестве {g, g2 , ..., g } являются попарно несравнимыми по модулю p и составляют δ решений сравнения x 1mod p. Действительно, для всех 1 ≤ i ≤ δ имеем

gi g i 1mod p.

48

Все решения сравнения (2) находим, умножая по модулю p решение x0

на каждое из значений

g, g 2 mod p, ..., g mod p. Действительно,

для всех

1 ≤ i ≤ δ имеем x0 g

i

x0

a mod p. В силу равносильности сравнений (1)

и (2) в качестве решения первого сравнения имеем следующие δ

классов:

, x g2

, ..., x g .

x g

0

0

0

Таким образом, вопрос нахождения всех корней сводится к нахождению одного корня. Рассмотрим, как можно найти один корень третьей степени в

случае 3 | p –1. Пусть дано некоторое число a ≤ p – 1. Выполним следующие шаги:

p 1

Проверяем условие a 3 1mod p . Если это условие не выполняется, то корней не существует, т. е. число a является кубическим невычетом по модулю p.

Находим число g ≠ 1, относящееся по модулю p к показателю 3. Для это-

го числа имеем: g2 mod p 1,			g3 mod p 1.
Находим невычеты (b и c) третьей степени по модулю p, удовлетворяю-
	p 1			p 1
щие условиям b 3 g mod p			и c 3 g2 mod p (вычеты не могут удовле-

творять ни одному из этих условий, а любой невычет удовлетворяет одному из этих условий). Нахождение указанных невычетов следует осуществить путем случайного выбора чисел и проверки выполнимости заданных условий.

Выполняем Алгоритм 1, представленный на рис. 3. В результате полу-

чим значение x 3a mod p . Алгоритм 1 включает как составные части Ал-

горитмы 2 и 3, представленные в виде блок-схем на рис. 4 и рис. 5.

49

Начало

s	p 1	;	t 0;	u 0
3

Нет
	s mod 3 = 0
Нет	Да
s mod 3 = 2
s mod 3 = 1

Да

s s / 3; t t / 3 ; u u / 3 ;

d asbt cu mod p

	Алгоритм 2	Алгоритм 3
			Нет	Да
				d 1 mod p
		Нет		Да
			d g mod p
		d g2 mod p
		t t p 1		u u p 1
		3		3
		p 1		p 1
	Конец	db 3 1mod p
				dc 3 1mod p

Рис. 3. Схема алгоритма вычисления кубического корня из вычета a по простому модулю p (общий случай)

Работа Алгоритма 1 основана на поиске тройки чисел (s, t, u), таких что выполняется условие asbtcu 1mod p и при этом число s не делится на 3, а t и u делятся на 3. Если такая тройка чисел найдена, то мы имеем: либо s ≡ 2 mod 3, либо s ≡ 1 mod 3. В первом случае мы можем вычислить число

			s 1 t				u
		x a 3 b3c 3 mod p ,
которое и есть искомый корень третьей степени из числа a по модулю p.
Действительно,	возводя	x	в				третью		степень,	получаем:
x3 as 1btcu a mod p .
			50