Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
a) зависит только от класса вычетов по модулю р, к ко-
торому принадлежит а;
ь>(*) = (0(0!
c) если b up взаимно просты, то = (р)'
d) (i) = 1.(?)= (-I)"-1".
Доказательство. Свойство а) непосредственно следует из определения. Свойство Ь) следует из предложения II. 2. 2, так как пра-
(р-1)/2,(р-1)/2 , ,ч(р-1)/2 „ „
вая часть сравнима с а "о = (ab) , как и левая. Свой-
ство с) следует непосредственно из свойства Ь). Первое равенство свойства d) очевидно, так как 1 =1. Второе равенство d) вытекает из следствия 2 предложения II. 2.1 (или из предложения II. 2.2 с а = —1). Предложение доказано.
Часть Ь) предложения П. 2. 3 показывает, что можно определить, является ли а квадратичным вычетом по модулю р, т. е. вычислить
^p)) если разложить на множители число а и найти символы Лежандра сомножителей. Первый шаг к этому — записать а как произведение степени 2 и нечетного числа. Рассмотрим теперь, как вычисляется
(О-
Предложение II. 2.4. Имеет место соотношение
(T] - (-i)(P2-1)/8 _ J если P = ±1 (mod 8),
Vp/- ^ ' I"1. если р = ±3 (mod 8).
Доказательство. Пусть f(n) = ( — l)^n 1^8 при п нечетном, f(n) = 0 при п четном. Мы хотим показать, что ^jQ = f(p).
Из различных доказательств мы выберем эффективный метод, основанный на том, что нам уже известно о конечных полях. Так как р2 = 1 (mod 8) для любого нечетного простого р, то поле Fp2 содержит примитивный корень 8-й степени из единицы. Обозначим его ?. Заметим, что ?4 = -1. Положим G = Ej=o f(J)?J (G — пример того, что называется гауссовой суммой). ТогдаС = ?—?3—?5+?? = 2(?—tf) (так как ?5 = ?4? = f = -?3) и G2 = 4(?2 - 2?4 + f) = 8. Поэтому в поле Fp2 имеем:
G" = (G2)(P'1)/2G = 8(P~1)/2G =(1) G= (j) G
§ 2. КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ЗАКОН ВЗАИМНОСТИ
51
согласно предложению П. 2.2 и предложению И. 2.3 с). С другой стороны, используя определение G, соотношение (a + b)p = ар + bp, справедливое в Fp2, а также очевидное равенство f(j)p = f(j), находим, что Gp = Ej=o fU)CJ- Легко проверить, что /(;') = f(p)f(pj). Произведем теперь замену переменных j' = pj (ясно, что по модулю 8 индекс j так же, как и j, пробегает 0,1,..., 7). Тогда
Gp = J2 Mf(Pi) Є1 = Kp) E fW) = Яр) g.
j = 0 j' = 0
Сравнение двух равенств для Gp дает желаемый результат (деление на G возможно, так как G = 8, т.е. G ф 0 в Fp2).
Далее мы будем иметь дело с простыми нечетными делителями числа а. Обозначим такой нечетный делитель через q. Внимание: в оставшейся части параграфа q всегда будет обозначать простое нечетное число, отличное от р, а не степень р, как это было в предыдущем параграфе.
Число а в силу предложения П. 2. За) мы всегда можем считать меньшим р, поэтому и его простые делители q будут меньше р. Следующее предложение — фундаментальный квадратичный закон взаим-
ности — связывает и J- Последний символ Лежандра считать легче, так как можно заменить р его наименьшим положительным вычетом по' модулю д, следовательно, свести к символу Лежандра для меньших чисел. Квадратичный закон взаимности утверждает, что
(р) И (?) Н6 совпадают между собой, только если и р, и q сравнимы с 3 по модулю 4: в этом случае они противоположны по знаку. Это условие можно выразить формулой, используя тот факт, что (р—l)(g—1)/4 нечетно лишь тогда, когда р, q = 3 (mod 4), а в остальных случаях четно.
Предложение II. 2. 5 (Квадратичный закон взаимности). Пусть р, q — два нечетных простых числа. Тогда
(І) = ^1)(P-IX«-!)/« (R) = /"(?)' еслир = 3 (mod 4);
\Р/ \9/ I (2I в остальных случаях.
; в остальных случаях.
Доказательство. Опубликовано несколько дюжин доказательств квадратичного закона взаимности. Мы дадим весьма короткое доказательство в духе предыдущего предложения, используя конечные поля. Пусть / — такая степень р, что = 1 (mod q). Мы можем, например, всегда полагать / = q — 1. Как мы установили в
52
ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ
начале параграфа (предложение П. 2.1), поле Fp/ содержит примитивный корень q-й степени из единицы, который мы обозначим ? (напомним, что здесь q обозначает отличное от р простое число, а не р^). Определим «гауссову сумму» G формулой G = (g) fJ- Ниже
мы докажем лемму о том, что G2 = {-l)iq-1)/2q. Покажем сначала, как с ее помощью получается нужный нам результат. Это доказательство очень похоже на доказательство предложения П. 2. 4. Во-первых (применяя лемму, которая будет доказана ниже), мы находим, что
Gp = (G2f-1)/2G=((-l)('-1)/2,)(H)/2G
= ^_1)(p-1)(9-1)/49(p-1)/2g, _ ^_1^(p-l)(g-l)/4 ^9^ Q
согласно предложению II. 2.2 с q вместо а (напомним, что мы действуем в поле Fp/ характеристики р и поэтому сравнения по модулю р становятся равенствами). С другой стороны, из определения G, равенства (a + b)v = ар + Ьр в поле Fp; и очевидного соотношения
4.
Я-1 , .V q-l
J = O 4 4 / J = O
в силу частей Ь) и с) предложения П. 2. 3. Вынося (^j за знак суммы и меняя порядок суммирования (j —> j' = pj), приходим к соотношению Gp = ( - ) G. Приравнивая два выражения для Gv и производя деление
