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

3) раскладываем a в произведение степеней простых чисел, используя

			a			p1	a1		pk	at
	мультипликативность символа Лежандра:				=			K			, затем удаляем
						p			p
			p
	сомножители, являющиеся (ненулевыми) квадратами;

					2			p2 −1
	4) выделяем двойки, например, если	p1	= 2	, вычисляем			= (−1)	8 ;
					p

5)для каждого нечетного сомножителя pi применяем квадратичный закон взаимности (уменьшаем величины участвующих в вычислениях чисел);

6)при необходимости переходим к п.1.

	Пример.
	126			20			2	2	5		26 2		53			− 2	2	3
			=			=					= (−1)				=		= (−1) (−1) = −1
				53			53		53				5
	53															5

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

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

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

8.1.2. Символ Якоби

k

Пусть n нечетно и имеет следующее каноническое разложение n = ∏piai .

i=1

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

Символ Якоби числа x по модулю n, при (x,n)=1, определяется как

x				x	a1		x		at
произведение значений символов Лежандра			=			K				. Он обладает
				p			p
n
				1				k

практически всеми теми же свойствами, что и символ Лежандра, но по значению символа Якоби, равному единице, нельзя утверждать, что соответствующий вычет

– квадратичный.

Для квадратичного вычета, тем не менее, символ Якоби равен единице.

Следовательно, если nx = −1, то x - квадратичный невычет по модулю n .

Пусть x, x1, x2 - целые, n1,n2 - нечетные числа, большие единицы.

Свойства символа Якоби.

x1 = x2 (n) xn1 = xn2 ;

	x x			x		x
		1 2		=	1		2	;
		n			n		n

(x2 ,n)=1 x22 x1 = x1 ;n n

1

−1

(n−1) 2

=1

,

=

(−

1)

;

n

n

x

x

x

=

;

n n

n

n

1

2

1

2

2

n2 −1

= (−1)

.

8

n

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

m			(m−1)(n−1)			n
нечетных чисел m>1 и n>1 выполняется равенство			= (−1)	4			.
	n				m