4.5. Примеры

В качестве непосредственной иллюстрации рассмотренных теорем исследуем разложение двоичного многочлена

Это разложение справедливо над любым полем. Над двоичным полем (полем из двух элементов) и — взаимозаменяемы и потому

Множитель является неприводимым двоичным многочленом второй степени. Для разложения этого неприводимого многочлена надо расширить поле так, чтобы включить корни многочлена. Если обозначить через один из его корней, то

Другой корень этого квадратного многочлена, а именно является двоично сопряженным с Обозначим его через д. В GF(4) имеем полное разложение

Здесь

и

Четыре элемента поля могут быть представлены как четыре двоичных многочлена от (или ), степени которых три ненулевых элемента поля могут быть представлены в виде соответствующих степеней (или ).

В качестве более поучительного примера рассмотрим разложение двоичного многочлена и несколько связанных с ним представлений поля Начнем с разложения на круговые многочлены:

Это разложение справедливо над любым полем. Читателю предлагается проверить, что

В двоичном поле многочлен распадается на два примитивных неприводимых квадратных многочлена 1). Одним из методов определения этих множителей является метод исключения. множителя могут быть записаны в виде где двоичные числа. Так как 1 не является корнем многочлена, то должно выполняться условие так что либо три коэффициента либо только один из них равны 1. Первый случай исключается, так как приводит к Наконец, -

так что

Более простой метод определения двух неприводимых делителей многочлена базируется на том факте, что если и то преобразование и переводит сопряженные элементы в сопряженные и неприводимые многочлены в неприводимые. Например, в рассматриваемом случае многочлен неприводим, и, значит, неприводим многочлен Так как этот неприводимый трехчлен не делит то он должен делить Другой делитель многочлена есть многочлен взаимный с этим делителем. Любой из методов дает следующее разложение над :

Расширяя двоичное поле присоединением корней многочлена

(см. скан)

получим поле Разложение над имеет вид

Читатель должен отметить, что появляются в разложении сопряженными парами аналогично тому, как при разложении действительных многочленов на комплексные множители появляется пара Происходит это по той же причине. Комплексно сопряженные числа представляют собой корни одного и того же действительного неприводимого многочлена сопряжены, поскольку они являются корнями одного и того же неприводимого двоичного многочлена

Очевидно, что распадается над на четыре неприводимых линейных и шесть неприводимых квадратных множителей; читатель может проверить это методом исключения.

Таблица 4.1 (см. скан)

Для последующего разложения необходимо дальнейшее расширение поля до дающее те 12 элементов поля которые не входят в Не ограничивая общности, обозначим эти дополнительные 12 элементов различными греческими буквами:

Так как а — один из восьми корней многочлена то он примитивный элемент и каждый из 15 ненулевых элементов ноля может быть записан в виде степени а. Эти результаты приведены в столбцах 1 и 2 таблицы 4.1.

Так как а — корень неприводимого над квадратного многочлена то каждый элемент поля можно

представить в виде многочлена от а над степень которого Соответствующие результаты приведены в столбце 3.

Соответствующие строчки столбца 3 могут быть получены с помощью представленного на рис. 4.1 регистра с обратной связью, если позаботиться о том, чтобы правильно выполнялись все арифметические операции поля Для этого необходимо использовать равенства

Используя столбец 3, можно отождествить остальные элементы поля Ясно, что совпадает с элементом сопряженным с а относительно ; равно равно сопряжены с а относительно но не относительно Следовательно, они — корни одного и того же неприводимого двоичного многочлена четвертой степени и разных неприводимых квадратных многочленов над Эти элементы обозначены через (в произвольно выбранном порядке).

Рис. 4.1. Регистр сдвига с обратной связью над

Так как а и — корни квадратного уравнения то они являются также корнями многочлена следовательно, корни квадратного уравнения Такими элементами являются Аналогично корни многочлена , и они совпадают с Наконец, нам осталось определить, с какими из пар или сопряжены корни многочленов относительно поля Так как то заключаем, что это у и 0, а это Таким образом, получаются 16 элементов, список которых приведен в столбце 5. Они являются корнями соответствующих неприводимых многочленов над записанных в столбце 4. Отметим, что, не меняя столбца 4, можно переименовать любую пару сопряженных относительно элементов.

В столбце 6 для каждого из 16 элементов выписаны минимальные двоичные многочлены. Они получаются непосредственно из разложения неприводимых двоичных многочленов четвертой степени на неприводимые квадратные многочлены над Заметим, что произвольный элемент, его квадрат, его четвертая степень и его восьмая степень являются корнями одного и того же неприводимого двоичного многочлена.

Так как а является корнем неприводимого двоичного многочлена четвертой степени то можно пренебречь подполем и выразить каждый элемент поля как двоичный многочлен от а степени Такое представление приведено в столбце 7. Соответствующие степени а найдены как подходящие состояния регистра сдвига с обратной связью для умножения на а; см. рис. 4.2.

В большинстве случаев наиболее удобными являются представления, приведенные в столбцах 1 и 7. В машинной обработке используется почти исключительно представление, записанное в столбце 7. Однако при ручных вычислениях полезными оказываются оба представления. Умножение, деление, возведение в степень и извлечение корня более удобно выполнять в терминах представления, заданного в столбце 7.

В столбце 8 приведена двоичная запись логарифмов ненулевых элементов по основанию а. Такая запись имеет несколько преимуществ. Например, двоичный логарифм мультипликативного обратного к элементу поля получается путем поэлементного дополнения двоичного логарифма самого элемента. Единственной особенностью является появление последовательности единиц в качестве дополнения к нулевой последовательности, представляющей двоичный логарифм единицы. Такая единичная последовательность должна также пониматься как двоичный логарифм единицы. Нулевая и единичная последовательности являются эквивалентными представлениями одного и того же числа, подобно тому как и —0 являются в действительности одним и тем же числом. По существу арифметикой двоичных логарифмов является так называемая арифметика «дополнения до единиц», которая повсеместно используется в определенных тйпах вычислительных программ и арифметических блоках.

Рис. 4.2. Регистр сдвига с обратной связью для умножения на а.

Другим более важным преимуществом двоичной записи логарифмов является то, что двоичный логарифм каждого из двоично сопряженных элементов может быть получен с помощью циклического сдвига двоичного логарифма самого элемента. Например, двоичные логарифмы сопряженных элементов равны векторам , каждый из которых является левым циклическим сдвигом своего предшественника. Аналогично двоичные логарифмы сопряженных элементов являются двукратными циклическими сдвигами друг друга.

В полях характеристики -ичные логарифмы обладают такими же преимуществами, какими обладают двоичные логарифмы в полях характеристики 2.

Выбор примитивного элемента а, через который выражаются все остальные элементы поля, является несколько произвольным.

В столбце 9 приведена реализация, связанная с выбором другого корня неприводимого примитивного двоичного многочлена четвертой степени. В столбце 10 выписано представление элементов поля в виде двоичных многочленов от степени . В столбце 11 дается иное представление элементов поля в виде линейных комбинаций элементов Аналогичным образом все элементы поля могут быть представлены в виде линейных комбинаций любых четырех линейно независимых элементов поля, т. е. четырех элементов, для которых все 16 двоичных комбинаций различны, или, иначе, элементов, для которых ни одна ненулевая линейная комбинация не равна нулю. Некоторые множества из четырех элементов, как, например, удовлетворяющие уравнению а не являются независимыми. Множество из четырех линейно зависимых элементов поля нельзя выбирать в качестве базиса для представления поля.

Четыре элемента поля, используемые в качестве базиса представления, выписанного в столбце И, а именно представляют собой полное множество двоично сопряженных элементов. Поэтому, используя этот базис, можно возводить в квадрат и извлекать квадратные корни из элементов поля, используя только перестановку позиций в представлении. Возведение в квадрат выполняется с помощью левых циклических сдвигов, а извлечение квадратного корня — с помощью правых циклических сдвигов. В отношении этих операций столбец 11 подобен столбцу 8. Однако на этом аналогия кончается. Представление, выписанное в столбце 11, и представления в столбцах 7, 10 и 15, являются линейными: сложение элементов может быть выполнено покомпонентно. Представление, приведенное в столбце 8, этим свойством не обладает; сложение двух элементов поля, заданных только представлением столбца 8, составляет существенную проблему. В терминах представлений столбцов 7, 10, 11 и 15 сложение является тривиальным, однако умножение значительно сложнее. Возведение в квадрат наиболее просто выполнимо в терминах представления, выписанного в столбце 11, но умножение двух произвольных элементов является более сложным. Поэтому практически наиболее часто используется представление элементов поля в виде двоичных многочленов от некоторого корня неприводимого двоичного многочлена.

В столбце 12 сделана попытка представления элементов поля в виде степеней непримитивного элемента у, являющегося корнем многочлена и не являющегося корнем Представление ошибочно, так как и имеется только пять различных степеней у. Однако в столбцах 13 и 14 выписаны допустимые представления ноля через степени у и смежные классы. Различный выбор лидеров смежных классов по подгруппе этих степеней в столбцах 13 и 14 иллюстрирует тот факт, что два смежных класса либо не пересекаются, либо полностью совпадают.

В столбце 15 выписано представление элементов поля в виде двоичных многочленов от у степени Так как у — корень неприводимого двоичного многочлена четвертой степени, то это представление допустимо несмотря на то, что этот многочлен не примитивен.

Интересно остановиться на изображенном на рис. 4.3 регистре сдвигов с обратной связью, предназначенном для умножения элементов поля на у в данном представлении.

Рис. 4.3. Регистр сдвига с обратной связью для умножения на

При любом начальном состоянии регистр проходит через каждое из остальных четырех состояний, входящих в смежный класс начального состояния, и затем возвращается в исходное положение.

В столбцах 16 и 17 выписаны следы элементов поля относительно подполей и . След в относительно часто обозначаемый через Определяется соотношением

Так как

Как будет видно из теоремы 6.69, след дает информацию о решении в данном поле некоторых квадратных и кубических уравнений.