Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Доказательство. Любой элемент F9 можно записать как степень д3 образующего элемента д. Степень элемента д равна 1 в том и только том случае, когда ее показатель делится на q — 1. Таким образом, д3 — корень п-й степени из единицы, если и только если Jn =
48
ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ
О (mod q - 1). Далее, пусть d = НОД (n,q - 1). Согласно следствию 2 из предложения 1.3. 1 сравнение nj = 0 (mod q — I) относительно j эквивалентно сравнению = О (mod 3^p). Так как ^ и взаимно просты, последнее сравнение эквивалентно тому, что j кратно (д -I)Id. Другими словами, d различных степеней элемента д^ч~^/а — это в точности корни п-й степени из 1. Число таких корней равно п тогда и только тогда, когда d = п, т.е. n|(g — 1). Наконец, если n\(q — 1), то полагаем ? = </9 1^". Тогда ?J = 1 тогда и только тогда, когда n\j. Далее, к-я степень ?J равна 1 тогда и только тогда, когда kj ~ 0 (mod п). Нетрудно заметить, что ?J имеет порядок п (т.е. последнее сравнение не выполняется ни при каком положительном к < п) тогда и только тогда, когда j и п взаимно просты. Таким образом, при n|(g - 1) существует tp(n) различных примитивных корней п-й степени из единицы. Доказательство завершено.
Следствие 1. Если НОД (n,q — 1) = 1, то 1 есть единственный корень п-й степени из единицы.
Следствие 2. Элемент —1 Є F9 имеет квадратный корень в F9 в том и только том случае, когда q = 1 (mod 4).
Следствие 1 — частный случай предложения. Чтобы доказать следствие 2, заметим, что квадратный корень из —1 — это то же самое, что примитивный корень четвертой степени из 1, а необходимое и достаточное условие его существования — это 4|(g— 1).
Следствие 2 утверждает, что при q = 3 (mod 4) мы всегда можем получить квадратичное расширение F92, присоединяя корень много-члена X + 1, т.е. путем рассмотрения выражений типа «гауссовых целых чисел» а + Ы. Мы проделали это при q = 3 в предыдущем параграфе.
Предположим, например, что р — простое число и р = 3 (mod 4). Имеется красивый способ рассмотрения поля Fp2, который обобщается также на другие ситуации. Пусть R обозначает кольцо гауссовых целых чисел (см. упражнение 14 к §1.2), Иногда используется запись R = Z + Zi, подразумевающая, что R состоит из всех линейных комбинаций элементов 1 и г с целыми коэффициентами. Если т — произвольное гауссово число, а = а + Ы, ? = с + di — два гауссовых целых, то пишем а = ? (mod тп), если а — ? делится на тп, т.е. если частное (а — ?)/m есть целое гауссово число. Мы можем рассматривать множество R jmR совершенно так же, как кольцо классов вычетов в случае обычных целых чисел: при сложении и умножении получающийся класс вычетов не зависит от того, какие представители были выбраны в слагаемых (или сомножителях). Если теперь т = р + Ог есть простое число и р = 3 (mod 4), то, как нетрудно
§ 2. КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ЗАКОН ВЗАИМНОСТИ
49
заметить, R/pR — не что иное, как поле Fp2.
Квадратичные вычеты. Пусть р — нечетное простое число, т.е. р > 2. Нам интересно знать, какие из ненулевых элементов {1,2, ...,р— 1} в Fp являются квадратами. Если а Є F* — квадрат, скажем, a = b2, то а имеет в точности 2 квадратных корня ±6 (так как уравнение X — а = 0 имеет в поле не более двух решений). Таким
* 2
образом, все квадраты в Fp можно найти, вычисляя b по модулю р для b = 1,2,...,(р— 1)/2 (каждое из остальных чисел сравнимо с — Ь для некоторого из этих 6), т.е. в точности половина элементов
* 2 2
Fp — квадраты. Например, квадраты в F11 — это 1 = 1, 2 =4, З2 = 9, 42 = 5, 52 = 3. Квадраты в Fp называются квадратичными вычетами по модулю р. Остальные ненулевые элементы называются невычетами. Для р = 11 невычеты — это 2, 6, 7, 8, 10. Имеется (р — 1)/2 вычетов и (р — 1)/2 невычетов.
Если g — образующий в Fp, то любой элемент можно записать как gJ. Тогда квадрат любого элемента имеет вид д1 с четным j. Обратно, любой элемент д3, где j четно, есть квадрат: д3 = (+д^2)2.
Символ Лежандра. Пусть а — целое число и р > 2 — простое число. Символ Лежандра определим равенством
' 0, если р\а,
1, если а — квадратичный вычет по модулю р, 1, если а — невычет по модулю р.
Таким образом, символ Лежандра — это просто способ обозначать, является данное целое число квадратичным вычетом или невычетом по модулю р.
Предложение II. 2. 2. Имеет место соотношение
Q = а(р-1)/2 (mod р).
Доказательство. Если а делится на р, то обе части соотношения сравнимы с нулем по модулю р. Пусть р /а. По малой теореме Ферма квадрат а^р~1^2 в Fp есть 1. Поэтому а'р 1^2 = ±1. Пусть g — образующий в F* и a = gJ. Как мы видели, а — вычет тогда и
тт (р-1)/2 Лр-1)/2 1
только тогда, когда j четно. Далее, а = <7 равно 1 в том
и только том случае, когда Jp~y~ делится на р — 1, т. е. когда j четно. Таким образом, обе части в сравнении равны ±1 в Fp, и каждая из них равна +1 тогда и только тогда, когда j четно. Предложение доказано.
50
ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ
Предложение II. 2.3. Символ Лежандра обладает следующими свойствами:
