08.04.09.Печать_edit

Во втором случае значение s + 2 делится на 3 и мы можем вычислить число

		s 2		t		u
	a
		3	b	3	c	3	mod p,
x

которое представляет собой кубический корень из квадрата числа a: x 3 as 2btcu mod p a2 mod p.

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

		mod p 2		s 2		t u
x 2
	x		a 3		b3 c 3 mod p,

которое представляет собой кубический корень из a или из – a. Покажем, что x′ есть квадратичный вычет, а, значит, приведенная выше формула корректна.

а)	Начало	б)	Начало
	s s 1		s s + 2

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

dasbt cu mod p x d1 mod p

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

dasbt cu mod p x 2d mod p

Нет	x3 mod p a	Да

x 3 a mod p	x p a
Конец	x 3 a mod p	Конец

Рис. 4. Две версии Алгоритма 2: а — с вычислением обратных значений и б — с извлечением квадратного корня по модулю p

51

Очевидно, что значение x′ 3 является квадратичным вычетом по модулю

3

p 1

p 1 3

2

1mod p

2

1mod p . Если предполо-

p, т. е. для него имеем x

x

p 1

жить,

что

x′ есть квадратичный

невычет,

2

1mod p

то x

p 1

3

2

1mod p . Полученное противоречие доказывает наше предпо-

x

ложение. Очевидно, что

x3 2 as 2btcu 2 a2

a mod p , поэтому вы-

численное значение x следует возвести в третью степень. Если x3 a mod p,

то корень кубический найден. Если x3 – a mod p, то корень кубический ра-

вен 3 a p x .

Начало

Для случая s ≡ 1 mod 3 может быть приме-

нен более эффективный альтернативный алго-

s s + 1

ритм вычисления искомого корня. Он основан

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

;

на том, что значение s – 1 делится на 3 и мы

можем вычислить число

d asbt cu mod p

s 1

t

u

3

3

c

3

mod p

,

x a

b

d 3 a mod p

которое представляет собой кубический корень

из числа a –1 mod p:

Конец

x 3

as 1btcu mod p a 1 mod p .

Рис. 5. Блок-схема Алгоритма 3.

Искомый корень равен

1 s

t

u

3

1

mod p a

3

b

3

c

3

mod p .

a x x

Действительно, имеем:

x3 a1 sb tc u as 1btcu 1

a mod p .

Работу Алгоритма 1 можно пояснить следующим образом. При инициа-

лизации устанавливаются значения s p 1 , t = 0 и u = 0, поэтому перемен-

3

ная d asbtcu mod p вначале имеет значение 1. Если s делится на три, то мы

52

s t u

можем получить значение корня из d: d 3d 3asbtcu a 3b3c 3 mod p , которое может оказаться равным (в зависимости от случайно выбранных нами значений невычетов b и c): либо 1, либо g, либо g 2 mod p 1. Рассмотрим эти три случая.

Случай d ≡ 1 mod p. Снова выполняется проверка делимости s на число 3. Если 3 | s, то еще раз извлекаем корень кубический из d ≡ 1 mod p (это осуществляется тремя операциями присвоения s s / 3 , t t / 3 и u u / 3 ).

Случай d = g. Осуществляется «виртуальное» умножение текущего зна-

p 1

чение d на g 2 mod p c 3 mod p (это соответствует выполнению операции

присвоения u u p 1 ), а затем проверяется условие 3 | s; если 3 не делит s,

3

то осуществляется переход к выполнению Алгоритма 2 или Алгоритма 3.

Случай d g2 mod p 1. Осуществляется «виртуальное» умножение (по модулю p) текущего значение d на g, что соответствует выполнению опера-

ции присвоения t t p 1 , а затем проверяется условие 3 | s; если 3 не де-

3

лит s, то осуществляется переход к выполнению Алгоритма 2 или Алгоритма 3.

Нетрудно заметить, что в момент, когда будет получено значение s, которое не делится на 3, значения t и u будут кратными числу 3. Поэтому операции t t / 3 и u u / 3 в Алгоритмах 2 и 3 сохраняют целочисленные значения переменных t и u.

Алгоритм 1 даст на выходе одно значение кубического корня. Остальные два следует найти путем умножения полученного корня 3a mod p на g

и g2 mod p. Какое из трех значений корня будет получено на выходе Алгоритма 1, зависит от выбора конкретных значений невычетов b и c.

Аналогичным образом для случая 5 | p – 1 можно составить алгоритм для вычисления корня 5-й степени по простому модулю, при этом в нем потребуется использовать алгоритмы извлечения корней 2-й и 3-й степеней. Затем перейти к составлению алгоритма для вычисления корня 7-й степени, в котором будет использован алгоритм вычисления корней 5-й степени и т. д.

53

В общем случае для вычисления корня простой степени q | p – 1 потребуется использование алгоритмов вычисления корней всех простых степеней, меньших степени q. Если степень корня составная, то достаточно использовать только алгоритмы вычисления корней степеней, не превышающих значение максимального простого множителя заданной составной степени.

2.3.3. Случай модуля, равного степени простого числа

Для полноты еще следует рассмотреть вопрос извлечения корней по модулю равному степени простого числа для случая когда степень корня делит функцию Эйлера от модуля. Данная задача решается аналогично случаю извлечения корней по простому модулю. Это определяется тем, что по модулю

ps , где– нечетное простое число, существуют первообразные корни. Их су-

ществование определяет ряд свойств вычетов по модулю ps аналогичных свойствам вычетов по модулю p.

Утверждение 2.1.

Пусть для некоторого числа a имеем НОД(a, (ps)) = 1, где p – нечетное простое число. Тогда a является вычетом степени n | ps 1(p 1) по модулю

ps тогда и только тогда, когда a	ps 1 ( p 1)
	n	1mod ps .
Доказательство.

Необходимость. Пусть a – вычет, т. е. существует некоторое значение x, такое что выполняется сравнение xn a mod ps . По модулю ps имеются первообразные корни. Пусть g – один из них. Тогда указанное степенное сравне-

ние можно представить	в виде gn ind x gind a mod ps ,	откуда	следует
n ind x ind a mod ( ps ) ,	где (ps) = ps 1(p 1). Поскольку по		условию
модуль делится на n, то из последнего сравнения следует,		что n | ind a , т. е.

индекс вычета n-й степени делится нацело на n. Поэтому существует решение записанного выше степенного сравнения, т. е. имеем корень

	ind a				x ps 1 ( p 1)				ind a	ps 1 ( p 1)
x g n mod ps							g		n
gind a			ps 1	( p 1)		ps 1 ( p 1)
				n	a n			mod ps
					54

Согласно теореме Эйлера, имеем

ps 1

ps 1( p 1)

x

( p 1)

1mod p

s

a

n

1mod p

s

.

ps 1( p 1)

Достаточность. Пусть

a

n

1mod p

s

. Покажем, что тогда a – вы-

чет степени n по модулю ps. Пусть g – некоторый первообразный корень. То-

ps 1( p 1)

ps 1( p 1)

ind a

ps 1

гда имеем a

n

g

n

mod p

s

и 1 g

( p 1)

mod p

s

. Теперь ус-

ps 1( p 1)

ind a

ps 1

ловие задачи можно представить в виде g

n

g

( p 1)

mod p

s

, сле-

довательно, имеем

ps 1( p 1)

ind a ps 1( p 1) mod ps 1( p 1)

n | ind a .

n

Поэтому можем записать a gind a

ind a n

mod ps , т. е. число a предста-

g

n

ind a

вимо в виде n-й степени числа x g n mod ps , а значит, оно является выче-

том n-й степени по mod ps .

Утверждение 2.2.

Число классов вычетов степени n | ps 1(p 1), где p – нечетное простое число, по модулю ps равно n.

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

Рассмотрим сравнение xn a mod ps , где НОД(a, (ps)) = 1 и a – вычет n-й степени по mod ps . Пусть g – некоторый первообразный корень. Тогда можем переписать указанное сравнение в виде gn ind x gind a mod ps , откуда следует n ind x ind a mod ( ps ) , где (ps) = ps 1(p 1). Поскольку по ус-

ловию модуль (ps) делится на n, то из последнего сравнения следует, что

n | ind a ind a nQ , где nQ ps 1( p 1) Q ps 1( p 1) , т. е. имеем ко- n

55

	личество различных целых чисел Q, равное	ps 1( p 1)	(значит число классов
		n

вычетов степени n не превосходит последней дроби), и им соответствуют разные значения gnQ mod ps , соответствующие различным классам вычетов по модулю ps, причем все из последних являются вычетами степени n по mod ps . Действительно, gnQ gQ n mod ps . Поэтому число классов, являю-

щихся вычетами степени n по mod p	s	, равно	ps 1 ( p 1)	.
			n

Рассмотрим случай задачи нахождения квадратных корней по mod ps . Пусть a и b являются квадратичным вычетом и квадратичным невычетом по модулю ps, соответственно. Пусть также при некоторых целых значениях степеней t и z, причем s является нечетным, а z – четным, выполняется сравнение

	atbz 1mod ps .										(2.1)
Тогда имеем:
at 1bz a mod ps						t 1 z			2	a mod ps
		a 2 b2									,
т е. значение
def	t 1 z
x a 2 b 2 mod ps											(2.2)

является решением сравнения x2 a mod ps . Такой же подход использовался нами ранее для нахождения корней по простому модулю. Действуя далее по

				ps 1( p 1)
					2		s
аналогии и используя условие		a					1mod p , запишем исходное сравне-
ние
	ps 1( p 1)				ps 1 ( p 1)
	2							s
a			b				1mod p .		(2.3)

Если в (2.1) степень при a нечетна, то мы найдем корень по формуле (2.2). Если нет, то тогда делим степени при a и b на два (это соответствует извлечению корня из левой части). После этого левая часть (2.3) может ока-

56

заться равной 1 или 1 по mod ps . Это следует определить вычислительным путем. Если будет получено значение 1, то умножаем полученное выраже-

		ps 1( p 1)
		2	s
	ние на b		1mod p (покажите, что это сравнение имеет место для

любого невычета). После этого опять получаем сравнение вида (2.1), причем, если s делится на 2k, то z делится на 2k + 1 (k – натуральное число). Действуя таким путем мы найдем представление единицы в виде atbz mod ps при некотором нечетном s и четном z, а затем по формуле (2.2) вычислим один из квадратных корней.

Таким же путем можно найти корни из квадратичных вычетов по mod 2 ps . Алгоритмы для вычисления корней более высоких степеней могут быть также построены по аналогии со случаем решения аналогичной задачи по простому модулю.

2.4. Трудный случай извлечения корней по простому модулю

2.4.1.Модуль со специальной структурой

Внекоторых случаях извлечение корней по простому модулю является трудной задачей. Подобным случаем является вычисление корней большой

степени k по простому модулю вида p = Nk2 + 1, где N – большое четное число, s 2 и k – простое число достаточно большого размера. Трудность нахождения корней по составному модулю n ранее использовалась при разработке широко известных и применяемых на практике двухключевых шифров: RSA, криптосистемы Рабина и некоторых других. Однако сложность решения задачи извлечения корней по модулю определяется трудоемкостью задачи факторизации, после решения которой извлечение корней по составному модулю сводится к решению задачи извлечения корней по простым модулям q и r.

Для произвольно выбранных значений степени корня k и простого модуля p для любого вычета a степени k вычисление всех значений корня из a по mod p является сравнительно простой задачей. Если k не делит p 1, то существует обратный элемент k 1 mod p = k и имеется единственный корень ka ak mod p . Если k|p 1, то существуют k корней. При этом, если k2|p – 1, то вычислительная сложность этой задачи становится достаточно высокой, а

57

при длине степени корня |k| = 160 бит и более – практически неразрешимой (далее мы покажем, что при этом значение |N| следует выбрать равным 704 бит и более, поскольку задача извлечения корня может быть решена посредством решения задачи дискретного логарифмирования).

Сложность решения задачи извлечения корней по простому модулю связана с некоторыми фактами, вытекающими из следующих трех известных утверждений:

1. Существуют	p 1		различных вычетов a j степени k (j = 1, 2, ...,	p 1	).
	k			k

p 1

2.Для любого вычета a степени k имеем: a k

3.Для некоторого невычета bi имеем:

mod p 1 .

p 1

k mod p e , где

b

e k 1mod p и i = 1, 2, ..., k 1.

i

i

i

Из этих фактов следует следующее

Утверждение 2.3.

Каждому корню из единицы

e соответствует ровно

p 1

различных

i

k

p 1

p 1

mod p e .

значений b , где j = 1, 2, ...,

, таких что b k

ij

k

ij

i

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

Действительно,

пусть

для

bij

и

bij

выполняется

p 1

p 1

p 1

k

b k

mod p b k mod p e . Тогда имеем:

bij

mod p 1, т. е. отношение

ij

ij

i

b

ij

bij

есть вычет степени k по модулю p. Поскольку существует ровно

p 1

bij

k

различных вычетов a j , то существует ровно столько же различных значений

bij .

2.4.2. Вычисление корня большой простой степени

Из утверждения (2.3) следует, что, выбирая случайное значение t, мы имеем следующие вероятности:

58

p 1

p 1

Pr t

k

mod p 1

Pr t

k mod p e

i

для всех i = 1, 2, ..., k 1. Пусть выбран случайный вычет a. Очевидно, что

p 1

значение a

k 2

mod p принадлежит множеству e ,e ,...,e

,1 . Число степенных

1 1 k 1

p 1

вычетов a, для которых имеем a k 2 mod p 1 равно значению

p 1

Z1 # a : p (a)

N , где # обозначает мощность множества {*} и

k 2

p (a) обозначает порядок числа a по модулю p. Число вычетов, для которых

p 1

p 1

Z .

имеем

a k 2 mod p 1,

равно

Z

2

Известно

[1],

что

k

1

# a : p (a) d (d )

и

(N ) N ,

где (N ) - значение функции

d|N , d 0

Эйлера

от

числа

N,

следовательно

Z1 N

и

Z

p 1

N Nk N N (k 1) .

Получаем,

что

вероятность

2

k

p 1

Z1

1

k 2

k

2

Pr

пренебрежимо мала и с вероятностью

a

mod p 1

Z2

k 1

k 1

p 1

мы имеем a k 2

mod p 1

, где

e - некоторый корень из единицы, не равный

i

1.

Учитывая,

что

для

каждого i

существует некоторый

i',

такой

что

p 1

e 1 mod p ,

e

мы можем записать

a k 2 e

1mod p ,

поэтому для некоторого

i

i

i

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

p 1

p 1

a k 2 b k aN bNk 1mod p .

(2.4)

Если сравнение (2.4) выполняется, то можно легко вычислить z ka mod p . Действительно, сравнение (2.4) можно представить в виде

akbNk ak N mod p ,

(2.5)

где с достаточно высокой вероятностью имеем НОД( k N , p 1) = 1 (в противном случае задача несколько усложнится, так как потребуется дополнительно вычислить корень сравнительно малой степени, однако в целом ее

59

решение не будет сложным). В рассматриваемом случае можно вычислить значение N k N 1 mod p 1 и затем

akN bNkN	a mod p,
aN bNN k	a mod p.	(2.6)

Сравнение (2.6) показывает, что величина aN bNN mod p есть один из корней z ka mod p . Вопрос состоит в нахождении невычета b, удовлетворяющего сравнению (2.4). Заметим, что значение b может быть представлено в виде bibj 1mod p , где bi и bj некоторые невычеты. Действительно, любой ко-

рень из единицы можно представить в виде произведения двух других корней из единицы, поэтому имеем:

		aNbNkbNk 1mod p aNbNk				b Nk mod p		(2.7)
		i j			i	j
Следующий алгоритм позволяет с достаточно высокой вероятностью
найти значения bi и bj , удовлетворяющие сравнению (2.7).
1. Выбрать случайное значение bi . Вычислить и сохранить в таблице 1
значения b и	A aNbNk mod p		для i 1,2,...,		, где				и [*]
				k				k
i	i	i

обозначает целую часть значения *. (Сложность этого шага составляет при-

мерно

k

операций модульного экспоненциирования.)

2. Выбрать случайное значение bj . Вычислить и сохранить в таблице 2

bNk mod p для

j 1, 2,...,

.

значения

b

j

и B

j

k

(Сложность этого

j

шага составляет примерно

операций модульного

k

экспоненциирова-

ния.)

3. Упорядочить таблицу 1. (Сложность этого шага составляет примерно

| k |

k

операций сравнения, | k | обозначает битовую длину числа k.)

4. Для j 1,2,...,

k

проверить, если в таблице 1 содержится значе-

ние A B

| k | операций

j

. (Сложность этого шага составляет примерно

k

i0

сравнения.)

60