ПРИЛОЖЕНИЕ В. ТАБЛИЦЫ НЕПРИВОДИМЫХ МНОГОЧЛЕНОВ НАД ПОЛЕМ GF(2)

В этом приложении даются таблицы, с помощью которых можно найти все неприводимые над GF (2) многочлены степени 16 или меньше. В таблицах указаны некоторые свойства этих многочленов и соотношения между ними. Приводятся примитивные многочлены с минимальным числом ненулевых коэффициентов и многочлены, принадлежащие всем возможным показателям для каждой степени от 17 до 34.

Многочлены даны в восьмеричном представлении. Каждый символ в таблице обозначает три двоичных знака в соответствии со следующим кодом:

Коэффициенты многочленов в двоичной записи расположены в порядке убывания, так что коэффициент при слагаемом высшего порядка расположен слева. Например, 3525 обозначает многочлен 10-й степени. В двоичной записи числу 3525 эквивалентно число и соответствующий многочлен равен

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

Буквы, которые приведены после восьмеричного представления многочлена, дают о нем следующую информацию:

(см. скан)

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

Примеры. Первой записью в таблице неразложимых многочленов 6-й степени является примитивный многочлен (103), или Если а обозначает "корень то корень многочлена (127) и ось корень многочлена (147). Минимальным многочленом для является многочлен степень которого равна 3, т. е. меньше шести.

В таблице нет записи, соответствующей Другими корнями минимального многочлена для элемента являются Таким образом, минимальный многочлен для совпадает с минимальным многочленом для т. е. с многочленом (147). В таблице нет записи, соответствующей Другими корнями минимального многочлена для элемента являются и один из этих корней не входит в таблицу. Корнями двойственного многочлена к многочлену являются элементы . В качестве минимального многочлена для в таблице указан многочлен (155) или Минимальным многочленом для является, таким образом, многочлен, двойственный и этому многочлену, т. е. многочлен

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

С другой стороны, порядок равен показателю, к которому принадлежит минимальная функция для Так, например, в элемент имеет порядок 93, так как

Таким образом, многочлен (3453) принадлежит показателю 93.

Марш [50] опубликовал таблицу всех неприводимых многочленов степени 19 или меньше над В этой таблице многочлены

расположены в лексикографическом порядке — это наиболее удобный способ для Определения того, является ли данный многочлен неприводимым.

Многочлены минимального веса в приводимой ниже таблице для степеней, не превосходящих 19, были найдены по таблицам Марша. Для степеней от 19 до 43 многочлены минимального веса были найдены методом испытаний и ошибок, при котором рассматривался каждый Тйногочлен веса 3, потом каждый многочлен веса 5 и т. д. Для того чтобы проверить, является ли многочлен степени примитивным, применялась следующая последовательность операций.

1. Находятся вычеты по модулю

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

3. Для каждого сомножителя в разложении числа вычет для образуется перемножением подходящей комбинации нычетон. найденных на этапе. Если все эти вычеты не равны 1, то многочлен является примитивным.

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

Таблица В.1. (см. скан) Разложение на простые сомножители

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

ПРИЛОЖЕНИЕ Г. РЕКОМЕНДУЕМЫЙ ПОРЯДОК ЧТЕНИЯ КНИГИ

(см. скан)

ПРИЛОЖЕНИЕ Д. СПИСОК ОБОЗНАЧЕНИЙ

(см. скан)

ЛИТЕРАТУРА

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)