<< Предыдущая

стр. 5
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

жество обозначается через ?р[х] и образует кольцо относительно
естественных операций суммы и умножения многочленов.
Особый интерес представляет случай р = 2^ откуда мы и будем
черпать наши примеры в данном параграфе. Например, в кольце
?2[х] выполнены равенства:
{1 + х + х'^)-\-{х + х^) = 1-\-х'^ -\- х^,
{1 + х + х^) ' (х-^х^) =x-i-x'^ -^-х"^ + х^.
Можно зафиксировать многочлен f{x) и рассматривать осталь­
ные элементы кольца ?р[х] по модулю^ / ( ^ ) - Как и натуральные чи­
сла по модулю 7V, возможные остатки будут образовывать кольцо.
Оно обозначается через
?p[x]/f{x)?p[x] или ?p[x]/{f{x)).

^То есть оперировать с остатками от деления многочленов на f{x). — Прим.
перев.
1.2. Конечные поля

Пусть, например, f (х) = х"^ + 1 и р = 2. Тогда
{l + x + x'^) '{х + х^) (modx^ + 1) = 1 + ж^,
так как
X + ж^ + ж^ + ж^ - (ж 4- 1) • (ж^ + 1) + (1 + х^).
Проверяя выписанные равенства, следует помнить, что все коэффи­
циенты рассматриваются по модулю 2.
Напомним, что при знакомстве с целыми числами по модулю N
нас интересовало уравнение
ах = b (modTV).
Можно поставить аналогичный вопрос и для многочленов. Пусть а,
Ь и / — многочлены из Fp[a:]. Существует ли решение уравнения
аа = b (mod/)
относительно неизвестной а? Здесь, как и в целых числах по модулю
ЛГ, ответ зависит от наибольшего обш;его делителя многочленов а и
/ и возможны три ситуации. Самая интригуюш;ая из них возникает
при взаимно простых а и / , т. е. когда ПОД (а, / ) = 1.
Многочлен называется неприводимым^ если у него нет делите­
лей, отличных от него самого и констант. Таким образом, неприво­
димость многочленов — это то же самое, что простота целых чисел.
Напомним, что целые числа по модулю N образуют поле, только ес­
ли T — простое число. Точно так же, кольцо ?p[x]/{f{x)) является
V
конечным полем тогда и только тогда, когда многочлен f{x) непри­
водим.
Предположим, что р = 2 и рассмотрим два неприводимых мно­
гочлена
/ l ( x ) = Ж^ + X + 1 и / 2 = Х^ + Х^ + 1.

У нас возникают два конечных поля
Fi=?2[x]/{Mx)) и Г2 = ?^[х]/{/2(х)),
каждое из которых состоит из 2^ двоичных многочленов^, степень
которых не превосходит 6. Сложение в обоих полях выглядит оди­
наково, поскольку при вычислении суммы складываются коэффици­
енты многочленов по модулю 2. А вот умножаются элементы этих
^Действительно, любой такой многочлен имеет ровно 7 коэффициентов, равных
О или 1. Поэтому число всех многочленов — 2^. Легко понять, что в общей ситуа­
ции поле ?p{x)/{f{x)) насчитывает р^ элементов, где п — степень неприводимого
многочлена f(x). — Прим. перев.
Глава 1. Сравнения, группы, конечные поля и вероятность

полей по-разному:
{х^ + 1) • {х^ + 1) (mod/i(x)) =х^ + х^ + х,
{х^ + 1)-[х^^1) {modf2{x))=x\
Возникает любопытный вопрос: действительно ли различны поля
Fi и F2, или это только кажущееся различие? На математическом
языке вопрос формулируется так: изоморфны ли поля Fi и F2? Го­
ворят, что поля Fi и F2 изоморфны, если существует отображение
(р : Fi —> F2, называемое изоморфизмом^ которое удовлетворяет
двум требованиям:


Оказывается, изоморфизм существует между любыми двумя конеч­
ными полями с одинаковым числом элементов. В частности, он су­
ществует и между нашими полями Fi и F2. Мы не будем доказывать
здесь этого факта, но отметим, что для построения изоморфизма
между Fi и F2 достаточно показать, как выражается корень f2{x)
в виде многочлена от корня fi{x).
Приведенные выше конструкции по существу одинаковы и дают
единственный способ построения конечных полей. Следовательно,
все конечные поля фактически совпадают либо с целыми числами
по простому модулю, либо с многочленами по модулю неприводимо­
го многочлена (который тоже можно называть простым). Конечно,
имеет место равенство ?р = ?р[х]/{х). Так что можно утверждать
единственность конструкции конечных полей. Итак, мы приходим
к фундаментальной теореме.

Теорема 1.6. Существует единственное (с точностью до изомор­
физма) конечное поле с числом элементов, равным степени простого
числа.
Будем обозначать поле из q = р^ элементов символом F^ или
GF{q). Обозначение GF{q) означает поле Галуа из q элементов. Так
(после XIX века) иногда называют конечные поля по имени фран­
цузского математика Галуа. У него была интересная жизнь. Галуа
написал свои блестящие работы в раннем возрасте и погиб на дуэли.
Нам необходимо объяснить несколько технических терминов, свя­
занных с конечными полями. Любое конечное поле К содержит в
себе экземпляр поля целых чисел по некоторому простому модулю
р. Это поле называется простым подполем поля К. Число р элемен­
тов простого подполя называется характеристикой поля и обозна­
чается через char if. В частности, charFp = р.
1.2. Конечные поля

На конечном поле характеристики р можно определить так на­
зываемое отобраэ/сение Фробениуса:


Легко проверить, что отображение Фробениуса — изоморфизм по­
ля F^ с самим собой. Такого сорта изоморфизмы принято называть
автоморфизмами. Интересное свойство автоморфизма Фробениу­
са заключается в том, что множество элементов из F^, остающихся
неподвижными при действии Ф, совпадает с его простым подпо-
лем, т.е.
{ae?q\ аР = а} = ?р.
Заметим, что это утверждение — обобщение малой теоремы Фер­
ма на случай любых конечных полей. Если х — произвольный авто­
морфизм конечного поля, то множество неподвижных относительно
него элементов тоже образует подполе, которое принято называть
неподвижным полем автоморфизма х- Таким образом, предыдущее
утверждение говорит о том, что неподвижное поле автоморфизма
Фробениуса совпадает с простым подполем F^.
К тому, что поле ?q содержит копию Fp, можно добавить, что
Fpd содержит подполе Fpe р^ля любого числа е, делящего d. Это под­
поле может быть определено как неподвижное поле автоморфизма
Ф^, т.е.
{ae?pd\ а^' = a } = Fpe.
Другое интересное свойство характеристики р поля F^ заключается
в том, что взяв произвольный элемент а G F^ и сложив его с собой
р раз, мы получим 0. Например в поле F49 имеет место равенство
Х + Х + Х + Х + Х + Х + Х = 7Х = 0 (mod 7).
Ненулевые элементы конечного поля, множество которых обычно
обозначается через F*, составляют конечную абелеву циклическую
группу. Образующая группы F* называется примитивным элемен­
том^ конечного поля. Подчеркнем, что примитивный элемент есть
в любом конечном поле, поскольку группа его ненулевых элемен­
тов всегда циклическая. Иначе говоря, всегда можно найти такой
элемент д ^?q^ что любой ненулевой элемент а G F^ будет предста­
вляться в виде


при некотором целом показателе х.
^Примитивных элементов, как и образующих циклических групп, может быть
несколько. — Прим. перев.
Глава L Сравнения, группы, конечные поля и вероятность

В качестве примера рассмотрим поле из восьми многочленов
F23 =?2[х]/{х^ -\-x-hl).

в нем существует семь ненулевых элементов, а именно
1, а, а + 1, а^, а^ Н-1, а^ + а, а^ + о^ + 1,
где а — корень многочлена^ х'^ + х -\- 1- Убедимся, что а — прими­
тивный элемент поля F23:
а^ = а,
= а^ = a^ + а, а^ = 1.
а^ =: Qf^, а^ = а^ + а + 1,
а^ = а + 1, a^ = a^ + l,
Отметим, что целые числа по модулю р также имеют примитивный
элемент, т. к. Z/pZ = ?р — конечное поле.


1.3. Основные алгоритмы
Существует несколько численных алгоритмов или технических при­
емов, которые следует знать каждому читателю, т. к. они часто ис­
пользуются в данной книге. Здесь мы сконцентрируем внимание на
- алгоритме Евклида,
- китайской теореме об остатках,
- вычислении символов Якоби и Лежандра.

1.3.1. Н а и б о л ь ш и й о б щ и й д е л и т е л ь
В предыдущем параграфе мы отмечали, что для решения уравнений
а ' X = b (mod N)
в целых числах или
аа = b (mod/)
в многочленах по простому модулю нам необходимо найти наиболь­
ший общий делитель. В частности, надо выяснить, имеет ли данный
элемент а G Z/NZ (или а E?p[x]/{f)) обратный элемент по умноже­
нию, т. е. выполнено ли равенство НОД (а, N) = 1 (соответственно
НОД (а, / ) = 1)? Мы не объяснили как вычислить этот наибольший

^Более точно, формальный корень, т.е. некий искусственно введенный элемент,
удовлетворяющий соотношению а^ + а + 1 = 0, в котором все действия выпол-
^удовлетворяющий +
няются по модулю 2. — Прим. перев.
1.3. Основные алгоритмы

общий делитель и не рассказали о методе построения обратного
элемента при условии его существования. Исправим наше упущение
описанием старейшего алгоритма, известного человечеству, а имен­
но, алгоритма Евклида.
Если бы мы могли разложить числа а и N на. простые делители,
а многочлены а и / на неприводимые множители, то вычислить наи­
больший общий делитель не составило бы труда. Пусть, например,
а = 230895 588 646 864 = 2^ • 157 • 4513^
Ь = 33 107 658 350 407 876 = 22-157-2 269^ - 4 513.
Из данного разложения мгновенно получается НОД:
НОД (а, Ь) = 2^ -157 -4513 = 2 834164.
Однако разложение на простые множители — очень трудоемкая опе­
рация, в то время как вычисление наибольшего общего делителя
сравнительно несложно, что мы сейчас и продемонстрируем.
1,3.1.1. Алгоритм Евклида. Здесь мы рассмотрим только слу­
чай целых чисел. Распространить его на многочлены несложно, по­
скольку как целые числа, так и многочлены обладают свойством
евклидовости: их можно делить с остатком. Разделить целое число
а на число b с остатком — это значит найти такие числа q и г с
О ^ г < |Ь|, при которых выполняется равенство
а = q ' Ь-Ь г.
Если мы хотим разделить многочлен / на многочлен д с остатком,
то нам нужно найти многочлены g и г, такие что^ О ^ degr < degg и
f =zq.g-^r.
Для вычисления наибольшего общего делителя чисел го = а и
Г1 = Ь мы последовательно вычисляем Г2, гз, Г4,..., производя деле­
ние с остатком по следующей схеме:
Г2 = qm + Го,
^3 = д2П2 + п ,


^ т ^^ Чт—1'^m—l ˜г ^т—2?


Очевидно, что если число d делит как а, так и Ь, то оно делит и все
^Напомним, что символ degg обозначает степень многочлена д, которая равна
наибольшей степени входящих в него мономов. — Прим. перев.
Глава 1. Сравнения, группы, конечные поля и вероятность

г^, начиная с г = О и заканчивая г — т. Следовательно,
Н0Д(а,6) = НОД (ro,ri) = ••• = Н О Д ( г „ _ ь г ^ ) = г^.
Продемонстрируем работу алгоритма на вычислении НОД (21,12),
равного, без сомнения, 3. Используя описанную схему, мы находим
искомый делитель за несколько шагов:
НОД (21,12) = НОД (21 (mod 12), 12) =
= НОД (9,12) =
= НОД (12 (mod 9), 9) =
= НОД (3,9) =
= Н0Д(9 (mod3),3) =
- Н О Д (0,3) =3.
Приведем пример и с большими числами.
НОД (1426 668 559 730,810 653 094 756) =
= НОД (810 653 094 756,616 015 464 974) =
= НОД (616 015 464 974,194 637 629 782) =
= НОД (194 637 629 782,32102 575 628) =
= НОД (32 102 575 628,2 022176 014) =
= НОД (2 022176 014,1 769 935 418) =
= НОД (1 769 935 418,252 240 596) =
= НОД (252 240 596,4 251 246) =
= НОД (4 251246,1417 082) =
= НОД (1417082,0) = 1417082.
Используя функциональный язык программирования, такой, напри­
мер, как Haskell, алгоритм Евклида легко реализовать на практике,
поскольку он естественно записывается в рекуррентном виде:

myGcd : : I n t -> I n t -> I n t
myGcd a b = gcdstep (abc a) (abc b)

gcdstep : : I n t -> I n t -> I n t
gcdstep a b
I a == 0 =b
I otherwise = gcdstep (b 'mod' a) a

Bo многих языках программирования, таких как Java, С или
пакетах компьютерной алгебры типа Maple из-за больших затрат
1.3. Основные алгоритмы

ресурсов рекуррентное определение функции может оказаться не
самым лучшим способом действия. К счастью, мы не обязаны реа-
лизовывать алгоритм Евклида именно как рекурсию. Например, на
Java мы можем написать:

s t a t i c p u b l i c long g c d d o n g a, long b)
{
a=Math.abs(a);
b=Math.abs(b);
while (a != 0)
{ long temp=by.a;
b=a;

<< Предыдущая

стр. 5
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>