Квадратичные сравнен второй степени. Квадратичные вычеты и невычеты. Символ Лежандра. Нахождение квадратного корня по модулю

НАЦИОНАЛЬНЫЙ  АВИАЦИОННЫЙ УНИВЕРСИТЕТ

           Институт информационно - диагностических систем

            Кафедра компьютеризованных систем защиты информации

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Лабораторная работа №3.3

Квадратичные  сравнен второй степени. Квадратичные вычеты и невычеты. Символ Лежандра. Нахождение квадратного корня по модулю.

 

 

 

 

 

 

 

 

 

 

 

Выполнил:                                                  студент группы  БИ-441

                                                                       

 

Проверила:                                                 асистент кафедри компьютеризованих

                                                                      систем защиты информации

                                                                       

 

 

 

 

 

 

 

 

 

 

Киев 2012

 

Цель: Научиться вычислять значение символа Лежандра, ознакомиться с основными его свойствами. Освоить методы нахождения квадратных корней квадратичного сравнения.

Задание

1. Изучить основные теоретические сведения.
2. С помощью критерия Эйлера установите, имеет ли решение сравнение значения выбрать согласно варианту, указанному преподавателем, из таблицы в приложении.
3. Вычислить значение символа Лежандра . Значения выбрать согласно варианту, указанному преподавателем, из таблицы в приложении. Сделать вывод о существовании квадратного корня числа по модулю .
4. Найти корни уравнения значения выбрать согласно варианту, указанному преподавателем, из таблицы в приложении.

Теоретические сведения

Алгебраические  сравнения вида:

                                                            (1)

  где НОД , называется квадратичным сравнением по модулю .

Число называют квадратичным вычетом по модулю , если сравнение (1) имеет решения. В противном случае называют квадратичным невычетом.

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

Пример.  Число 4 является квадратным корнем из числа 2 по модулю 7 , так как . Значит, 2 - квадратичный вычет. Напротив, число 3 является квадратичным невычетом по модулю 7 , так как сравнение решений не имеет, в чем нетрудно убедиться последовательным перебором полной системы вычетов:  .

Простое наблюдение:  Если  – квадратичный вычет по модулю , то сравнение имеет в точности два решения. Действительно, если  – квадратичный вычет по модулю , то у сравнения (1) есть хотя бы одно решение . Тогда – тоже решение, ведь . Эти два решения не сравнимы по модулю  .

Поскольку сравнение (1) есть сравнение второй степени по простому модулю, то больше двух решений оно иметь не может.

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

Рассмотрим  сравнение 

                                                           (2)

где где НОД , а является простым нечетным числом.

Теорема. Если для сравнения (2) является квадратичным вычетом по модулю , то это сравнение имеет два решения.

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

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

Критерий  Эйлера позволяет определить существование решения сравнения (2).

Если  - простое нечетное число, то число , взаимно простое с будет квадратичным вычетом по модулю тогда и только тогда, когда .

Пример. Докажем, что число 5 является квадратичным вычетом по модулю 29:

.

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

Символом  Лежандра называется числовая функция, определенная для простых нечетных и целых , которая равна:

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

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

0, если  кратно .

Символ  Лежандра обозначается как  :

 

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

1. Если , то .
5. Для канонического разложения числа исполняется свойство мультипликативности символа Лежандра:

6. Если числа  и - взаимнопростые, то
9. Закон взаимности квадратичных вычетов. Если и - простые нечетные числа, причем , то символ Лежандра
10. Если - нечетное и , то символ Лежандра 

Данные  свойства позволяют вычислить символ Лежандра, не решая квадратичное сравнение.

Методика  вычисления символа Лежандра

1. Если , то выделяем множители .
2. Находим каноническое разложение числа : 
3. Используя свойство (5), записываем символ Лежандра в виде:
4. Используя свойство (6), исключаем множители, являющиеся полными квадратами. Множители, содержащие в числителе 2, преобразуем согласно свойству (8).
5. Для каждого множителя с нечетным числителем пересчитаем символ Лежандра, используя свойство (9).
6. Если числитель символа Лежандра больше, чем знаменатель и является нечетным, то используется свойство (10).

Пример. Вычислим символ Лежандра .

1.

Согласно  свойству (5)

2. Согласно  свойству (2)

3. Согласно  свойству (8)

4. Согласно  свойству (10)

Значит, символ Лежандра .

Символ  Лежандра используется для повышения  эффективности определения возможности  решения квадратичного сравнения  как следствие данное квадратичное сравнение имеет решения если символ Лежандра и не имеет решения, если .

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

На  сегодняшний день точного метода для решения алгебраического  сравнения второй степени не существует. Но известна общая апроксимационная процедура.

Постановка  задачи. Необходимо решить сравнение вида .

Последовательность  решения:

1. Вычислить значение символа Лежандра . Если символ Лежандра равен -1, то решения сравнения не существует, в случае, если символ Лежандра равен 1, переходим к пункту 2.
2. Представить число в виде , где - нечетное, а .
3. Подбираем случайный квадратический невычет , такой что .
4. Определяем число .
5. Вычисляем . Находим приближенное значение сравнения :

.

Решение сравнения будем искать, как  , где .

6. Записываем число в виде . Числа принимают значения 1 или 0.
7. Рассчитываем значения коэффициентов . Для этого находим значение , используя расширенный алгоритм Эвклида (лабораторная работа № 3.2(!)). Рассчитываем значения параметров :

, .

Считается, что  . Тогда

, .

Записываем  общее решение сравнения  в виде .

Пример. Найдем решения сравнения .

1. Вычислим символ Лежандра  .

. Значит сравнение имеет решения.

2. . Значит, , а .

3. Выберем  . Докажем, что является квадратным невычетом по модулю 37:

.

4. Вычислим число 

5. Найдем приблизительное решение  сравнения:

6. Вычислим значение  . Запишем число в двоичной системе счисления: .

7. Вычислим  , используя расширенный алгоритм Эвклида:

Остатки	Частные

 

.

Вычислим  . Значит .

Тогда общее решение сравнения  :

.

Еще пример. Найдем решения сравнения .

1. Вычислим символ Лежандра  .

. Значит сравнение имеет решения.

2. . Значит, , а .

3. Выберем  . Докажем, что является квадратным невычетом по модулю 37:

.

4. Вычислим число 

5. Найдем приблизительное решение  сравнения:

6. Вычислим значение  . Запишем число в двоичной системе счисления: .

7. Вычислим  , используя расширенный алгоритм Эвклида:

 

 

 

Остатки	Частные

 

.

Вычислим  . Значит .

Вычислим  . Значит .

Тогда

Тогда общее решение сравнения  :

.

Вариант №7

№ варианта	Задание 2		Задание 3		Задание 4
	а	р	а	р	а	р
7	4	5	160	59	20	59

 

Ход работы

1. Критерий Эйлера

a=4 p=5

число 4 является квадратичным вычетом по модулю 5

2. Вычислить значение символа Лежандра .

a=160 p=59

        а)

б) 

в)

г)

д)

е)

3. Найти корни уравнения 

a=20 p=59

\

а)

 

имеет решения.

б) . Значит, , а .

      в) Выберем . Докажем, что является квадратным невычетом по модулю 59:

.

г) Вычислим число

      д) Найдем приблизительное решение  сравнения:

      е) Вычислим значение . Запишем число в двоичной системе счисления: .

       ё) Вычислим , используя расширенный алгоритм Эвклида:

Остатки	Частные
59 20 19 1 0	* * 2 1 19	1 0 1 -1 *	0 1 -2 3 *