Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
. я.
на 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). Тем самым мы получили закон взаимности для символа Якоби.