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

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

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


X — X. При J=I они совпадают с р элементами простого поля (это — частный случай q = р предложения П. 1.4, а именно, малая теорема Ферма). Неподвижные элементы а1' — это корни X4 — X, т.е. все элементы F9. Так как /-я степень а — тождественное отображение, сг должно быть взаимно однозначным. Обратным для а

является отображение а3" *: a \—> ар . Никакая меньшая / степень а не является тождественным отображением, так как при j < f не все

элементы F9 являются корнями многочлена X — X. Это завершает доказательство.

Предложение II. 1. 6. Если (в обозначениях предложения И. 1. 5) а — любой элемент F9, то все сопряженные с а над Fp элементы (т. е. элементы Fq, являющиеся вместе с а корнями нормированно-

42

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

го неприводимого многочлена с коэффициентами из Fp) имеют вид aj(a) = оҐ.

Доказательство. Пусть поле Fp(a) как расширение Fp имеет степень d, т.е. представляет собой копию Fpd. Тогда а удовле-

творяет уравнению А - X = 0 и ар - а ф О, каково бы ни было j < d. Таким образом, повторным применением а к а получаем d различных элементов. Теперь достаточно показать, что все они являются корнями того же самого нормированного неприводимого многочлена, что и а; в этом случае они составляют d его корней. Чтобы сделать это, достаточно показать, что если а — корень многочлена f(X) є Fp[A"], то и f(ap) = 0. Пусть /(A') = Т.а3Х\ а0 є Fp. Тогда 0 = f(a) = i^aja1. Возводя обе части в степень р, согласно лемме получаем 0 = E(ajQ,7)P- Но по малой теореме Ферма ар = Oy, и мы имеем 0 = 2^1aj(aPy ~ /(qp)j что и требовалось доказать.

Явные построения. До сих пор наши рассмотрения конечных полей имели теоретический характер. Единственным реальным примером были поля вида Fp = Z/pZ. Теперь мы обсудим, как следует работать с конечными расширениями Fp. Здесь нам следует повторить, как мы обращались с такими расширениями поля рациональных чисел Q, как поле Q(\/2). Это поле получалось, когда мы брали корень а уравнения А" —2 = 0. Затем мы рассматривали выражения вида а + &а, а,Ь є Q, которые обычным образом складывали и перемножали, лишь заменяя каждый раз а2 на 2 (в случае Q(-\/2) работаем с выражениями вида а + ba + со?, при умножении заменяя всякий раз а на, 2). Тот же самый общий подход можно применить к конечным полям.

Пример 2. Для построения F9 берем любой приведенный квадратичный многочлен в F3[A7"], не имеющий корней в F3. Перебирая все наборы коэффициентов и проверяя, не являются ли 0, ±1 Є F3 корнями получающихся многочленов, мы обнаруживаем лишь т]эи приведенных неприводимых квадратичных многочлена: X +1,X ±Х — 1. Если мы, например, берем корень многочлена X + 1 (его лучше обозначить г, а не et, — ведь мы фактически присоединяем то элементами F9 будут все возможные комбинации а + Ы, где a,b = 0,±1. Арифметические действия в F9 поэтому аналогичны арифметике гауссовых целых чисел (см. упражнение 14 к § I. 2) с той лишь разницей, что коэффициенты а,Ь принадлежат крошечному полю F3.

Заметим, что элемент г, который мы присоединим, не является образующим, так как его порядок 4, а не q — 1 = 8. Если, однако, мы присоединяем корень а многочлена X —X — 1, то можем получить все

§ 1. КОНЕЧНЫЕ ПОЛЯ

43

ненулевые элементы Fg, взяв последовательные степени а (напомним, что а всегда следует заменять на а + 1, так как а — корень уравнения X2 = X + 1): а1 = а, а2 = а + 1, а3 = -а + 1, q4 = -1, а = -а, а6 = —а — 1 а7 = а — 1, а8 = 1. Мы иногда будем называть такие многочлены, как X —Х — 1, примитивными, имея в виду, что каждый корень такого неприводимого многочлена является образующим элементом мультипликативной группы ненулевых элементов поля. В Fg имеется 4 = tp(8) образующих (по предложению П. 1.2): два корня X - X - 1 и два корня X +X-I (второй из корней X —Х — 1 сопряжен с а: с (а) = а3 — -а + 1). Остальные 4 ненулевых элемента — это ±г = ±(а + 1) (корни X + 1) и 2 ненулевых элемента ±1 поля F3 (корни нормированных многочленов X + 1 и А' — 1 степени 1).

Вообще, в любом конечном поле F?, q = р3", всякий ненулевой элемент а удовлетворяет единственному неприводимому нормированному многочлену над Fp некоторой степени d. Тогда поле Fp(a), полученное присоединением этого элемента к простому полю, есть расширение степени d, содержащееся в F9, т.е. это копия Fpd. Так как большое поле Fp/ содержит Fpd и поэтому является векторным пространством над Fpd некоторой размерности /', то число элементов в

Fp/ равно (раУ = р3', т.е. / = df. Следовательно, d\f. Обратно, для любого d\f конечное поле Fpd содержится в Fp/, так как любое решение уравнения Xр = X есть решение Xр = X (чтобы убедиться в этом, заметим, что если в левой части уравнения Xр = X заменить

f — J/d раз X на Хр , то получится соотношение Хр = X). Таким образом, мы доказали следующий результат.

Предложение II. 1.7. Подполя Fp/ — это поля Fpd для d\f. Если элемент а Є Fp/ присоединяется к Fp, то получается одно из этих полей.

Теперь нетрудно доказать формулу, которая используется при нахождении числа неприводимых многочленов данной степени.
Предыдущая << 1 .. 17 18 19 20 21 22 < 23 > 24 25 26 27 28 29 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed