Перечислите свойства числа Лежандра.

; ; ; ; ; ; ; ;

52. В чем заключается закон взаимности квадратичных вычетов?

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

53. Каким образом вычисляются корни квадратичного сравнения по простому модулю?

Символ Лежандра используется для повышения эффективности определения возможности решения квадратичного сравнения как следствие данное квадратичное сравнение имеет решения если символ Лежандра и не имеет решения, если . Извлечение квадратных корней по простому модулю Постановка задачи. Необходимо решить сравнение вида . Последовательность решения: Вычислить значение символа Лежандра . Если символ Лежандра равен -1, то решения сравнения не существует, в случае, если символ Лежандра равен 1, переходим к пункту 2. Представить число в виде , где - нечетное, а .Подбираем случайный квадратический невычет , такой что . Определяем число . Вычисляем . Находим приближенное значение сравнения : . Решение сравнения будем искать, как , где . Записываем число в виде . Числа принимают значения 1 или 0. Рассчитываем значения коэффициентов . Для этого находим значение , используя расширенный алгоритм Эвклида (лабораторная работа № 3.2(!)). Рассчитываем значения параметров : , . Считается, что . Тогда , . Записываем общее решение сравнения в виде .

Дата добавления: 2015-12-01