Лекции по криптологии / Y22_M02_L12

Лекция 12. Квадратичный закон взаимности Гаусса. Символы Лежандра и Якоби.

12.1.Определение и свойства символа Лежандра.

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

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

Основные свойства символа Лежандра.

;

Критерий Эйлера: ;

;

;

, ;

.

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

Символ Лежандра можно вычислить с помощью следующей последовательности действий.

1) Если , то выделяем сомножитель ;

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

3) раскладываем в произведение степеней простых чисел, используя мультипликативность символа Лежандра: , затем удаляем сомножители являющиеся квадратами;

4) выделяем двойки, например, если , вычисляем ;

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

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

Пример.

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

12.2. Определение и свойства символа Якоби.

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

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

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

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

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

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

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

;

;

;

, ;

;

.

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

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

Пример. Вычислим символ Якоби .

.