Глава 11. Линеаризированные многочлены и аффинные многочлены

11.1. Как найти их корни

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

Однако существует специальный класс многочленов, корни которых могут быть найдены значительно проще. Эти многочлены впервые исследовались [1933, 1934], который назвал их -многочленами, но мы в силу причин, которые станут ясными из теоремы 11.12, будем называть их линеаризированными многочленами.

11.11. Определение. Многочлен над называется линеаризированным, если

Если стандартный базис поля то отсюда получим важное утверждение.

11.12. Теорема. Пусть линеаризированный многочлен и где тогда

Используя для элементов стандартные выражения, получаем, что

Следовательно, коэффициенты разложения многочлена по стандартному базису могут быть получены путем умножения вектор-строки на -матрицу над

Рассмотрим, например, многочлен

над где — корень примитивного неприводимого двоичного многочлена Используя приведенные в приложении А таблицы логарифмов и антилогарифмов, получаем, что

так что X — двоичная -матрица вида

Если, например, необходимо найти корни многочлена

то это эквивалентно уравнению

что равносильно системе линейных двоичных уравнений

Эта система может быть решена с помощью методов, описанных в разд. 2.5. Ее решения — это . Следовательно, корни многочлена (10.62) в ; другие два корня лежат в

Многочлен (10.62) получается путем вычитания из линеаризированного многочлена константы. Многочлены такого вида мы будем называть аффинными.

11.13. Определение. Многочлен над называется аффинным, если и, где линеаризированный многочлен,

Как было видно из примера, корни произвольного аффинного многочлена над лежащие в поле могут быть найдены

путем решения системы линейных уравнений с неизвестными над полем

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

Согласно теоремам 6.69 и 6.695, уравнение имеет решение в тогда и только тогда, когда Пусть а — произвольный элемент поля степени над элемент, для которого Тогда для можно найти такое что

Для решения уравнения положим Тогда

Следовательно, если то два решения квадратного уравнения имеют вид

11.15. Пример. Рассмотрим квадратные уравнения над Если корень многочлена то Полагая легко проверить, что решениями уравнения (11.14) являются

Решения уравнения могут быть найдены с помощью схемы, изображенной на рис. 11.1. Если в ячейке появляется 1, то квадратное уравнение не имеет решений. Если в ячейке появляется 0, то два решения квадратного уравнения возникают в регистре регистре у.

Рис. 11.1. Схема для решения уравнения в поле

Например, если то в ячейке появится