6.3. Трехчлены над GF(2)

Методы, описанные в разд. 6.1 и 6.2, можно легко запрограммировать. Используя современную вычислительную машину, легко

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

Среди наиболее интересных двоичных многочленов следует выделить трехчлены Если элемент а представляет собой корень неприводимого двоичного трехчлена степени то первые степеней элемента а представляют собой особенно привлекательный базис для записи поля так как умножение на а может быть выполнено с помощью -ячеечного регистра, в обратную связь которого входит всего один сумматор с двумя входами (см. разд. 2.41). В вопросах кодирования наибольшую практическую ценность имеют поля, порядок которых не превосходит 212. Поля при представляют больше академический, чем практический интерес. Однако имеются некоторые другие области применения регистров с обратными связями (такие, как построение двоичных псевдослучайных последовательностей), где представляет практический интерес отыскание примитивных двоичных трехчленов максимально высокой степени.

Так как матрица соответствующая трехчлену, содержит очень мало единиц, то базис нуль-пространства матрицы удобно определять с помощью методов, описанных в разд. 2.6. Это значительно облегчает разложение двоичных трехчленов по сравнению с произвольными двоичными многочленами.

В некоторых приложениях получение точного разложения не существенно, а требуется лишь определить, приводим многочлен или нет. Методы разд. 6.1 или другие алгоритмы [Глизон, Мак-Рэй (не опубликовано)] позволяют достаточно полно решить этот вопрос. Используя алгоритм Мак-Рэя и вычислительную машину , Цирлер нашел все неприводимые двоичные трехчлены степеней 1000. Используя более поздние результаты о разложении чисел Брилхарт определил показатели многих неприводимых трехчленов Цирлера. Эти результаты опубликованы Брилхартом и Цирлером в 1969 г.

Хотя для любителей счета эти данные и представляют значительный интерес, полная картина здесь пока не ясна. Большинство известных результатов, подытоженных Голомбом [1967], относятся только к отдельным значениям пик. Не известно даже, существуют ли примитивные двоичные трехчлены сколь угодно высокой степени. Единственная общая нетривиальная теорема о двоичных трехчленах, доказанная Суоном [1962], определяет лишь четность числа неприводимых множителей трехчлена Мы приведем эту теорему в следствии 6.696. Представляется весьма сложной даже задача определения числа неприводимых двоичных трехчленов заданной степени, хотя, как видно из равенства 3.37 и задач 3.3 и 3.4, число неприводимых многочленов в других больших множествах определяется достаточно просто.