Пусть p – простое число, большее 2. Рассмотрим отображение
,
сопоставляющее каждому элементу поля его квадрат. На множестве ненулевых элементов поля Fp это отображение в точности «два-в-один», то есть если из ненулевого элемента x Î Fp можно извлечь квадратный корень, то таких корней у него ровно 2 и, кроме того, ровно половина элементов из являются полными квадратами. Полные квадраты в называются квадратичными вычетами по модулю p. Множество всех квадратичных вычетов по модулю p является подгруппой порядка (p – 1)/2 в мультипликативной группе . Элементы мультипликативной группы из которых нельзя извлечь квадратный корень, называются квадратичными невычетами.
Для выявления полных квадратов по модулю p вводится символ Лежандра
Он равен 0, если a делится на p, +1, если a – квадратичный вычет по модулю p, и – 1, если a – квадратичный невычет.
Символ Лежандра легко вычисляется по формуле
Но использование этой формулы сопряжено с вычислениями больших степеней и на практике предпочитают пользоваться законом квадратичной взаимности
Иначе говоря
При вычислении символа Лежандра большую помощь оказывают следующие дополнительные формулы:
Пример. С использованием разложения на множители вычислим символ Лежандра.
Извлечение квадратного корня из квадратичного вычета a по модулю p при помощи алгоритма Шенкса.
1. Выбрать наугад такое n, что
2. Пусть e, q – целые числа с нечетным q, удовлетворяющие соотношению p – 1 = 2eq.
3. Положим y = nq (mod p), r = e, x = a(q – 1)/2 (mod p).
4. Положим b = ax2 (mod p), x = ax (mod p).
5. Пока b ¹ 1 (mod p) делать:
· найти наименьшее число m, такое, что
· положить
· положить
6. Вывести x.
Если p = 3 (mod 4), то для извлечения квадратного корня из a можно использовать формулу
формула дает правильный ответ потому, что
.
Символ Лежандра определен только в случае простого знаменателя. Если же знаменатель составной, то вводится символ Якоби, обобщающий символ Лежандра.
Пусть n – нечетное число, большее 2 и
.
Символ Якоби определяется через символы Лежандра простых делителей числа n следующим образом
Символ Якоби можно вычислять так же, как и символ Лежандра, опираясь на тождество, выведенное из закона квадратичной взаимности:
где a = 2ea1 и a1 нечетно. Полезно помнить еще несколько формул, справедливых при нечетном n:
Это дает быстрый алгоритм вычисления символа Якоби и, соответственно, символа Лежандра, как его частный случай, без разложения на множители. Единственное, что нужно сделать – выделить максимальную степень двойки.