Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Предложение II. 1.1. Порядок любого а Є F* делит q - 1.
Первое доказательство. Пусть d — наименьшая степень а, для которой ad = 1. (Такая степень, действительно, существует, так как ввиду конечности F^ степени элемента а не могут быть все различны между собой, и если a = а3, j > г, то а3 ' — 1.) Пусть S обозначает множество {1, a,a2,..., ad 1J всех различных степеней а. Для любого Ь Є F* пусть bS обозначает смежный класс, состоящий из всех элементов вида Ьа? (например, 15 = S). Нетрудно заметить, что любые два смежных класса либо совпадают, либо не содержат общих элементов. (Действительно, пусть элемент Ь-^а из S принадлежит
также &2-5\ т.е. b^a — 620^• Тогда для любого Ь^а из b\S имеем Ьха = Ьіа+г 1 = b2dJ + ' '.) Каждый смежный класс состоит из d элементов. Объединение всех смежных классов исчерпывает F* — это означает, что F^ есть объединение попарно непересекающихся d-элементных подмножеств. Следовательно, d\(q — 1).
Второе доказательство. Покажем, во-первых, что aq~l = 1. Чтобы убедиться в этом, напишем произведение всех ненулевых элементов из F9. Таковых имеется q — 1. Так как при умножении на а любые два различных элемента остаются различными, то, умножив каждый элемент произведения на а, мы вновь получаем то же произведение (при другом порядке сомножителей). Однако при этом мы умножили произведение на а9 1. Следовательно, а4 1 ~ 1 (ср. с доказательством предложения 1.3.2). Пусть теперь d — порядок а, т.е. наименьшая положительная степень а, которая дает 1. Если бы q - 1 не делилось на d, т. е. q — 1 = bd + г, 0 < г < d, то
38
гл. ii. конечные поля и квадратичные вычеты
меньшее, чем d, число г обладало бы свойством а = а4 1 bd — \. Но это противоречит минимальности d. Доказательство завершено.
Определение. Образующим элементом д конечного поля F9 называется элемент порядка q — 1; это равносильно тому, что степени д пробегают все элементы F9.
Следующее предложение описывает одно из наиболее фундаментальных свойств конечных полей. Оно утверждает, что отличные от нуля элементы любого конечного поля образуют циклическую группу, т. е. все они суть степени одного и того же элемента.
Предложение II. 1.2. Каждое конечное поле имеет образующий элемент. Если g — образующий элемент F*, то д3 — также образующий тогда и только тогда, когда НОД (j,q—l) — 1. В частности, всего в F9 имеется tp(q— 1) различных образующих элементов.
Доказательство. Предположим, что а Є F9 имеет порядок d, т.е. ad = 1 и никакая меньшая степень а не равна 1. Согласно предложению II. 1. 1 число d делит 0-1. Так как ad есть наименьшая
1 2d,
степень, равная 1, все элементы а, а ,... ,а =1 различны между собой. Мы утверждаем, что элементы порядка d — это в точности те ip(d) значений а3, для которых НОД (j,d) = 1. Во-первых, так как все d различных степеней различны, они представляют собой множество всех корней уравнения Xd = 1 (см. п. 5 списка свойств полей в начале главы). Любой элемент порядка d должен тем самым быть среди степеней а. Однако не каждая степень а имеет порядок d, так как при НОД (j,d) = d! > 1 элемент а3 имеет меньший порядок: числа d/d'
и j/d' — целые, и поэтому (a3)d^d = (ad)3^d = 1. Обратно, теперь покажем, что а3 при НОД (j,d) = 1 имеет порядок d. Действительно, допустим, что НОД (j,d) = 1 и а3 имеет порядок d" < d. Тогда
/ d'\j , d'\d , , d'\HOa(j,d) d" , і
[a ) = (a ) = 1, следовательно, [a ) = a = 1 (доказы-
вается аналогично предложению 1.4.2). Ho ad ф 1, так как а имеет порядок d. Таким образом, а3 имеет порядок d тогда и только тогда, когда НОД (j,d) = 1.
Это значит, что если имеется элемент порядка d, то существует в точности ip(d) элементов порядка d. Итак, для всякого d\(q - 1) существуют лишь две возможности: либо элементов порядка d нет, либо таких элементов в точности <p(d).
Но каждый элемент имеет некоторый порядок d\(q— 1), и имеется либо 0, либо ip(d) элементов порядка d. Согласно предложению I. 3. 7 справедливо равенство X^K9-I)V(6O = 1 ~ ¦> пРавая часть которого совпадает с числом элементов в F9. Отсюда и из того, что каждый элемент имеет некоторый порядок, следует, что для каждого d\(q- 1)
§ 1. КОНЕЧНЫЕ ПОЛЯ
39
всегда имеется в точности <p(d) (и никогда — нуль) элементов порядка d. В частности, существует в точности <p(q — 1) элементов порядка q — 1. Как мы показали выше, если элемент д имеет порядок q — 1, то все остальные элементы порядка q — 1 — это такие степени gJ, что НОД (j,q — 1) = 1. Предложение доказано.
Следствие. Для каждого простого р существует такое целое число д, что его степени пробегают все ненулевые классы вычетов по модулю р.
Пример 1. Мы можем получить все вычеты по модулю 19 от 1 до 18, взяв степени 2. А именно, последовательные степени 2, приведенные по модулю 19 —это 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10, 1.
Во многих ситуациях при работе с такими конечными полями, как Fp, р — простое число, бывает полезно найти образующий элемент. Что получится, если выбрать элемент g Є Fp случайно? Какова вероятность того, что он будет образующим? Другими словами, какую часть от ненулевых элементов составляют образующие? В силу предложения П. 1.2, эта часть равна <р(р — 1)/(р— 1). Согласно формуле для (?(p-l) из следствия предложения I. 3. 3 эта дробь равна П(1~ I )> где произведение берется по всем простым делителям / числа р — 1. Таким образом, шансы найти образующий элемент путем случайного угадывания сильно зависят от разложения числа р — 1. Например, справедливо следующее утверждение.
