Глава 8.

ВЫЧИСЛЕНИЕ КВАДРАТНОГО КОРНЯ В ПРОСТОМ ПОЛЕ

Основное в этой главе…

Квадратичные вычеты по простому модулю……………….……………..104

Алгоритм нахождения квадратного корня в простом поле………...…109

x2 ≡ a(n), где x -

104 Глава 8. ВЫЧИСЛЕНИЕ КВАДРАТНОГО КОРНЯ В ПРОСТОМ ПОЛЕ

8.1. Квадратичные вычеты по простому модулю

Квадратичным сравнением называется сравнения вида неизвестный вычет.

Целое число a называется квадратичным вычетом по модулю n, если сравнение x2 ≡ a(n) разрешимо. Если сравнение разрешимо, то для составного модуля количество решений, как правило, больше двух.

Поиск решений квадратичного сравнения часто используется в криптографии.

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

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

поскольку,

если

x2 ≡ a(n), то a является квадратичным вычетом по модулю

любого простого делителя числа n.

Пусть

p

-

нечетное простое

число.

Очевидно,

при a = 0(p)

имеется

единственное решение сравнения x2 ≡ a(p):

x = 0(p).

Все

ненулевые

вычеты

по

модулю p находятся среди

чисел

±1,±2,K,±

p −1

,

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

их

квадраты

составляют

список

2

2

2

p −1

2

. Сравнение x

2

≡ a(p) имеет решение, если a принадлежит

1 ,2

,K,

2

этому списку.

Далее, сравнение x2 ≡ k2 (p) имеет два очевидных решения: ± k . Кроме того, количество решений не может превышать степени многочлена в левой части, т.е. двух.

Квадратичные вычеты в простом поле 105

Чтобы убедиться, что решений в точности два, достаточно показать, что k ≠ −k(p).Очевидно, если это не так, то 2k = 0(p), что верно только для

k = 0(p).

Заметим теперь, что в нашем списке квадратичных вычетов все вычеты

попарно	несравнимы. Действительно, если, например, a ≡ k2 ≡l2 (p) и
1≤ k < l ≤		p −1		, то сравнение x2	≡ a(p) имело бы четыре решения: ± k , ±l ,
		2

что невозможно. Таким образом, количество ненулевых квадратичных вычетов

равно	p −1	. Следовательно, количество квадратичных невычетов также равно
	2

p −1 2 .

8.1.1. Символ Лежандра

Пусть g - примитивный элемент поля GF(p). Тогда a - квадратичный вычет в том и только том случае, когда в представлении a = g j (p) число j -

четно.

Действительно, если x2 ≡ a(p), то дискретное логарифмирование дает разрешимое сравнение вида 2y = j(p −1), где модуль четен.

Существуют алгоритмы для определения, является ли данное число квадратичным вычетом по простому модулю или нет. Один из алгоритмов связан с вычислением значения т.н. символа Лежандра, который для нечетного

простого p определяется следующим образом.
				0, a ≡ 0 mod p
	a		=	1, x : x2	≡ a mod p a ≠ 0 mod p
p						2	≡ a mod p a	≠ 0 mod p
				−1, ¬x : x

106 Глава 8. ВЫЧИСЛЕНИЕ КВАДРАТНОГО КОРНЯ В ПРОСТОМ ПОЛЕ

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

	Основные свойства символа Лежандра.
						a
	a	= a(p) a1			=			;
	1		p
						p

Критерий Эйлера: ap ≡ a(p−1)2 mod p ;

ab

a

b

=

;

p

p

p

2

b

(a, p)=1

a

=

b

p

;

p

1

−1

(p−1) 2

=1

,

= (−1)

;

p

p

2

p2 −1

= (−1)

8

.

p

Кроме того, имеет место квадратичный закон взаимности Гаусса: для любых

(p−1)(q−1)

простых нечетных чисел

p и

q выполняется равенство

p

= (−1)

4

q

.

q

p

a

Символ Лежандра

можно

вычислить

с помощью

следующей

p

последовательности действий:

1)если a <0, то выделяем сомножитель −1 ;

p

2)приводим a по модулю p ;