Материал: Приложение 2

F(3³), F(5²).

Пусть теперь h = 1. Рассмотрим поле F(p) с элементами 0,1,2,...,p-1. Если исключить элемент 0, то для остальных элементов поля можно также определить, являются они квадратичными вычетами или невычетами. Ясно, что элемент a, 1 £ a £ p-1 будет квадратичным вычетом по модулю p тогда и только тогда, когда выполняется сравнение:

x² º a mod p, где x - также является элементом поля F(p).

Рассмотрим пример. Пусть p = 7. Тогда

1² º 1 mod 7; 2² º 4 mod 7; 3² º 2 mod 7; 4² º 2 mod 7; 5² º 4 mod 7; 6² º 1 mod 7. Таким образом, квадратичными вычетами являются числа: 1,2,4. А квадратичными невычетами числа: 3,5,6.

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

-x º p - x mod p. Поэтому все квадратичные вычеты по модулю p можно найти возведением в квадрат чисел 1,2,3,...,(p-1)/2. Таким образом для любого p имеется ровно (p-1)/2 квадратичных вычетов и столько же квадратичных невычетов.

Упражнения.

a) Найдите квадратичные вычеты и квадратичные невычеты по простым модулям p = 11,13,17,19,23.

Символ Лежандра для целого a и простого p > 2 определяется следующим образом:

0, если p делит a.

= í 1, если a - квадратичный вычет по модулю p

-1, если a - квадратичный невычет по модулю p.

Понятно, что a можно заменить любым целым числом, сравнимым с a

по модулю p, при этом символ Лежандра не изменится. Вычисление символа Лежандра удобно производить по формуле:

= a^(p-1)/2 mod p. Действительно, = 8² º -1 mod 5.

Упражнения.

Вычислите следующие символы Лежандра:

, , , , , .

Символ Якоби является обобщением символа Лежандра на случай произвольного нечетного модуля n > 2. Пусть число n представлено в канонической форме: n = p₁^s1p₂^s2...p_k^sk. Тогда символ Якоби определяется как произведение символов Лежандра:

= ^{s1 s2}... ^sk

Например, пусть n = 363825=3³5²7²11¹. Найдем символ Якоби для числа a = 863. Сначала найдем наименьший положительный вычет числа 863 по модулям p = 3,5,7 и 11.

863 º 2 mod 3; 863 º 3 mod 5; 863 º 2 mod 7; 863 º 5 mod 11.

Тогда символ Якоби можно вычислить следующим образом:

= ^{3 2 2 1} = ^{3 2 2 1} =

(2^1º -1 mod 3)³ (3² º -1 mod 5)² (2³ º 1 mod 7)² (5⁵ º 1 mod 11)¹ =

(-1)(1)(1)(1) = -1. Т.е. число 863 является квадратичным невычетом по модулю 363825.

Для произведения чисел выполняется свойство мультипликативности:

=

Тогда

= = .

Для некоторых значений a символ Якоби вычисляется без перевода n в каноническую форму следующим образом:

= 1; = (-1)^(n-1)/2; = (-1) ^(n2-1)/8. Квадрат!

При вычислении символа Якоби основное сведение выполняется на основе закона взаимности:

= (-1) ^(m-1)(n-1)/4 , где m и n - нечетные числа большие 2.

Если не выполняется сравнение m º n º 3 mod 4, то

= .

Если же это сравнение выполняется, то

= - .

Пример.

Определить, является ли число a = 369 квадратичным вычетом или квадратичным невычетом по модулю 247 ?

369 º 1 mod 4, поэтому можно вычислить:

= = = = = = -1.

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

Упражнения.

Определить символы Якоби в следующих случаях:

1. b) c) .

Для криптографических систем представляет интерес случай, когда n является произведением двух простых чисел p и q, т.е. n = pq. Требуется определить, является ли некоторое число a квадратичным вычетом или квадратичным невычетом по модулю n? Т.е. существует ли такое x, что выполняется сравнение:

x² º a mod n.

Некоторое число a будет квадратичным вычетом по модулю n = pq если и только если оно будет квадратичным вычетом как по модулю p, так и по модулю q. Если рассмотреть множество чисел: 1,2,3,..., n-1 и исключить из него все числа, кратные p и (или) q, то в точности половина из оставшихся чисел будет удовлетворять условию: = 1, а вторая половина будет удовлетворять условию: = -1. Более того, из чисел a, удовлетворяющих условию = 1 половина будет квадратичными вычетами, а именно такие числа a, для которых = = 1. Другая половина, для которых = = - 1, будет квадратичными невычетами.

Пример. Пусть p = 3, q = 5, тогда n = 15. Квадратичными вычетами по модулю 15 будут числа a = 1 и 4. Квадратичными невычетами будут числа a = 2 и 8.

Если известно, что некоторое a является квадратичным вычетом по модулю n = pq, но простые числа p и q неизвестны, то решение сравнения (нахождение x из сравнения): x² º a mod n является важной, но очень сложной задачей в криптографии с открытым ключом.