Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 28

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 22 23 24 25 26 27 < 28 > 29 30 31 32 33 34 .. 125 >> Следующая


. я.

на G (что возможно, так как G = dcq и потому не равно нулю в Fp/), получаем квадратичный закон взаимности.

Итак, остается лишь доказать следующую лемму.

Лемма. Справедливо равенство G2 = ( — 1)^9 l^2q.

Доказательство. Воспользуемся определением G, в одном из сомножителей G заменим индекс суммирования j на — к и заметим, что суммирование можно производить, начиная с 1, так как

^J=O. Мы можем записать

E(MvV* = (т) ЕЕ(эк

9-1 9-1 / .2, \

j=i k=i \ 4 I



§ 2. КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ЗАКОН ВЗАИМНОСТИ

53

здесь мы воспользовались частью d) предложения II. 2. 3, чтобы заменить на (-!)'9 1^2 и произвели замену переменных к —> jk во внутреннем суммировании (так как для каждого фиксированного j элементы jk пробегают вместе с к все ненулевые вычеты по модулю q, а слагаемые зависят только от соответствующих вычетов по модулю q). Мы далее используем часть с) предложения II. 2. 3, изменяем

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

по j, что дает G2 = (^) ?V ?^1 В обеих двойных суммах суммирование распространяется от 1 до q — 1. Но мы можем, не изменяя величины общей суммы, добавить слагаемые с j = 0: это равносильно прибавлению величины X^I=i )> которая равна нулю, так как число вычетов совпадает с числом невычетов. Поэтому двойная сумма принимает вид

к=1 КЧ/ J = O

Но при каждом к ф 1 внутренняя сумма равна 0 как сумма всех различных степеней примитивного корня if' из 1. В этом легко убедиться, заметив, что умножение такой суммы на ?' сводится к перестановке слагаемых, т. е. произведение такой суммы и — 1 ф 0 равно 0. Следовательно, вклад дает только слагаемое с к = 1, и мы в итоге получаем

G2 = (-l)(9-1)/2(-)2e° = (-l)(9-1)/2?.

J = O

Лемма доказана и, таким образом, доказан квадратичный закон взаимности.

Пример 1. Определить, является ли 7411 квадратичным вычетом по модулю простого числа 9283.

Решение. Так как 7411 и 9283 — простые числа, сравнимые с 3 по модулю 4, имеем (Щ^) = - (ffff) = ~~ (ИїТ) с°гласно предложению П. 2. 3, часть а). Так как 1872 = 24 • З2 • 13, согласно предложению II. 2.3, часть с), имеем - (^fyf) = — (74fr)- Применяем теперь квадратичный закон взаимности, учитывая, что 13 = 1 (mod 4):

~~ (74fr) = — (^13^) = ~~ (із) = —^ем самьм мы видим, что 7411 — невычет по модулю 9283.

Неудобство при подобном вычислении символа Лежандра заключается в том, что каждый раз верхнее число надо разлагать на множители, чтобы иметь возможность применить предложение II. 2. 5. Если наши числа астрономически велики, то это потребует чрезмерных затрат времени. К счастью, можно обойтись без какого бы то ни было

54

ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ

разложения (исключая выделение степеней 2, что сделать очень легко). Мы докажем сейчас обобщение квадратичного закона взаимности, применимое ко всем нечетным положительным целым числам, не обязательно простым. Но сначала введем определение, обобщающее определение символа Лежандра.

Символ Якоби. Пусть а — целое число, п — любое нечетное натуральное число. Пусть п = Pi1P22 •¦ -р"г есть разложение п на простые множители. Символ Якоби (^¦) определяется как произведение символов Лежандра по всем простым делителям числа п:

а\ / а\"' /а

п> \PlJ KPr

Важно иметь в виду: равенство (^) = 1 для составного п не означает, что а есть квадрат по модулю п. Например, (^•) = (|) (|) = ( — 1)(-1) = 1, однако нет такого целого числа, квадрат которого был бы сравним с 2 по модулю 15.

Обобщим теперь предложения II. 2. 4 и II. 2. 5 на символ Якоби.

Предложение II. 2.6. Для любого нечетного натурального п

-\ = (-1)("2-1)/8 п)

Доказательство. Пусть f(n), как и в доказательстве предложения II. 2. 4, обозначает функцию в правой части равенства. Легко заметить, что /(Ti1 га2) = f{n\)f{n2) Для любых двух нечетных чисел Пі и п2 (достаточно рассмотреть все возможности ДЛЯ 7i1 и п2 как вычетов по модулю 8). Но отсюда следует, что правая часть

равенства — это f(p\)ai • • • /(рг)°г = (рт) ''' (р^~) пРедложе"

нию II. 2. 4), что, по определению, равно (-).

Предложение II. 2. 7. Для любых двух натуральных нечетных чисел тип имеем

—) = (_1)(^-i)("-i)/4 (IL

п J \т

Доказательство. Заметим, во-первых, что если тип имеют общий множитель, то по определению символов Лежандра и Якоби обе части равны нулю. Поэтому можно считать, что НОД (т, п) = 1. Затем мы записываем т и п в виде произведений простых чисел: m = pip2 ¦¦¦Pr, п = qiq2 ¦ • ¦ qs (в записях могут встречаться повторения, если тип делятся на квадраты). Чтобы перейти от

іт) = IL,,- (?") к (т) = Щ,- (?-)' мы Должны rs раз применить

§ 2. КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ЗАКОН ВЗАИМНОСТИ

55

квадратичный закон взаимности для символа Лежандра. Число -1 получится столько же раз, сколько встретится случаев, когда как р; в разложении т, так и qj в разложении п сравнимы с 3 по модулю 4; а число таких случаев равно произведению числа простых сомножителей в разложении тп, сравнимых с 3 по модулю 4, и числа таких же простых сомножителей в разложении п. Значит, (^) = (^-) всегда, кроме случая, когда число простых сомножителей, сравнимых с 3 по модулю 4, в каждом разложении нечетно; в последнем случае (^) = — (~)• Но произведение нечетных простых (в частности, тп или п) сравнимо с 3 по модулю 4 тогда и только тогда, когда оно содержит нечетное число простых, сравнимых с 3 по модулю 4. Итак, в результате перехода от (2^) к (^¦) коэффициент —1 может возникнуть только при тп = п = 3 (mod 4). Тем самым мы получили закон взаимности для символа Якоби.
Предыдущая << 1 .. 22 23 24 25 26 27 < 28 > 29 30 31 32 33 34 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed