Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1



Скачать 40.31 Kb.
Дата03.06.2013
Размер40.31 Kb.
ТипДокументы
Квадратичные вычеты.
Пусть р- простое, а < р, р>2.

Определение 1. а – квадратичный вычет .

Пример 1. Пусть р = 7, тогда 1, 2, 4 – квадратичные вычеты, а 3, 5, 6 – не квадратичные вычеты:

(mod 7)

Теорема 1. Существует квадратичных вычетов и не квадратичных вычетов в GF(p). У каждого квадратичного вычета существуют два корня такие, что , где называется основным корнем.

Д о к а з а т е л ь с т в о. При следовательно, уравнение = x имеет не менее двух корней. Если , то



Тогда или -(n) или (n). Отсюда имеет ровно два значения корня квадратного или ни одного. Ровно половина ненулевых элементов GF(p) есть квадратичные вычеты.

Теорема 2. Если n = p q, где p, q – простые, то квадратичных вычетов по modn и у каждого квадратичного вычета 4 корня.

Пример 2. n = 35 = 5 7 квадратичных вычетов по
mod 35: 1, 4, 9, 11, 16, 29. Каждый квадратичный вычет имеет ровно 4 корня.

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

L(a, p) = 0, если р/а;

L(a, p) = 1, если а- квадратичный вычет по mod p;

L(a, p) = -1, если а- не квадратичный вычет по mod p.

Теорема 3. L(a, p) = .

Д о к а з а т е л ь с т в о.

  1. .

  2. а- квадратичный вычет, то есть . Тогда по теореме Ферма

.

Таких a ровно gif" align=bottom>. Рассмотрим уравнение

.

Любое а – его корень. Отсюда каждое a является корнем одного из сомножителей в следующем уравнении:

.

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

.

Тогда по основной теореме алгебры остальные а, не являющиеся квадратичными вычетами, являются корнями уравнения

.

Если а- не квадратичный вычет, тогда

.

Теорема доказана.

Определение 3. Пусть р- простое, g < p. g называется примитивным элементом мультипликативной группы поля GF(p) (или примитивным элементом по mod p), если 0 < n p-1 a: .

Пример 3. При p = 11, 2 есть примитивный мультипликативной группы GF(11).



Каждое число n(1; 10) может быть представлено в виде .

Для р = 11 числа 2, 6,7,8 являются примитивными элементами мультипликативной группы GF(11). Остальные не являются примитивными элементами.

Замечание. В GF(p) (p-1) примитивных элементов.

Нахождение примитивного элемента, вообще говоря, не является простой задачей. Примитивный элемент находится легко, если известна факторизация р-1. Пусть - простые множители р-1. Для того чтобы проверить, является ли g примитивным элементом по mod p, вычисляется . Если для некоторого i это число равно 1, то g- не примитивный элемент. Если это не выполняется ни для какого , то g- примитивный элемент.

Пример 4. При р = 11 имеем р - 1 = 10 = 2 5. Проверим, что число 2 является примитивным элементом мультипликативной группы GF(11).



следовательно, 2 – примитивный элемент. Проверим 3.



следовательно, 3 не примитивный элемент мультипликативной группы GF(11).

Похожие:

Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconСуммы гаусса и их приложения
Двучленные сравнения по простому модулю. Степенные вычеты. Квадратичные вычеты, символ Лежандра
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 icon1. Простое трансцендентное расширение ассоциативно-коммутативного кольца с единицей
Определение Пусть k и L – ассоциативно-коммутативные кольца с единицами. Кольцо L называется простым расширением кольца k с помощью...
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconКвадратичные формы и их применения
Определение. Квадратичной формой переменных,принимающих числовые значения, называется числовая функция вида
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconНеопределенный интеграл Пусть имеем функцию. Определение
Определение. Первообразной функцией называется функция, если имеет производную в любой точке и
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconНеопределенный интеграл Пусть имеем функцию. Определение
Определение. Первообразной функцией называется такая функция, которая имеет производную в любой точке и
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconОсновные теоремы о вычетах
Пусть n взаимно-простое с а число, а 0; r=0, r,…,r наименьшие неотрицательные представители различных классов вычетов mod n. Рассмотрим...
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconЛинейные операторы и квадратичные формы
Определение Отображение L из линейного пространства в линейное пространство называется линейным отображением, или линейным оператором,...
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconРешение. Пусть число, удовлетворяющее условиям задачи
Найдите все простые числа, квадрат которых, измененный на 1, тоже простое число. (Юрасов Дима)
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconОпределение производной Определение: Пусть функция y=f(x) определена в точке x
Дадим аргументу x приращение x, такое, чтобы не выйти из указанной окрестности. Найдем соответствующее приращение функции y и составим...
Квадратичные вычеты. Пусть р- простое, а < р, р Определение 1 iconРяды Фурье для периодических и непериодических функций Пусть функция определена на ℝ. Определение
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org