Глава 2. Арифметические операции по модулю неприводимого двоичного многочлена

2.1. Более подробно об алгоритме Евклида

В предыдущем разделе было показано, что для декодирования двоичных БЧХ-кодов необходимо уметь выполнять арифметические операции в поле классов вычетов по модулю неприводимого двоичного многочлена Ключевую роль в решении этой задачи и с теоретической, и прикладной точек зрения играет алгоритм Евклида.

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

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

Алгоритм Евклида основан на том факте, что любой делитель элементов должен делить также их сумму и разность. Более того, так как любой делитель делит также и любое его кратное, скажем то любой общий делитель должен делить также Наоборот, любой делитель делит Следовательно, если через обозначить наибольший общий делитель элементов (ниженазываемый н. о. д.), то Значит, отправляясь от начальной пары элементов можно найти новую пару элементов с тем же н. о. д. Если выбрать соответствующим образом множитель а, то задача отыскания н.о.д. новой пары элементов может быть упрощена по сравнению с исходной задачей. Заметим, что предыдущая аргументация относится в равной мере как к целым числам, так и к многочленам с коэффициентами из любого данного поля. В первом случае под н. о. д. подразумевается наибольший по абсолютной величине общий делитель; во втором

случае — общий делитель наибольшей степени. Единственность н. о. д. для многочленов (с точностью до постоянного множителя) будет установлена позже как следствие алгоритма деления. В обоих случаях н. о. д. обладает следующими важнейшими свойствами:

Если натуральные числа и то обычно полагают Тогда Таким образом, если уже получены числа где то можно так определить числа что

Здесь

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

Так как убывающая последовательность неотрицательных чисел, то существует такое натуральное что

Очевидно,

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

где Так как так что

Следовательно, можно взять и затем двигаться в обратном направлении, полагая

Проделав эти выкладки, получим для и равенство

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

Иную процедуру, избавляющую от запоминания промежуточных результатов, дает алгоритм 2.11.

2.11. Другой вариант алгоритма Евклида. Пусть заданы числа Положим

и будем далее вычислять согласно формулам

При вычисления прекращаются.

Легко проверить, что

и что

Начиная с и проводя вычисления по индукции в соответствии с этими тремя формулами, получим, что для всех

При эта формула дает и потому

Более того, можно сделать некоторые выводы о величинах Так как то, очевидно,

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

Эта вариация алгоритма Евклида называется вариантом непрерывных дробей. Название это объясняется тем, что

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

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

Алгоритм Евклида для многочленов над полем аналогичен алгоритму Евклида для чисел. Пусть даны многочлены

где

элементы поля Как и ранее, мы будем обозначать через степень многочлена (наибольшее , для которого Если то, используя алгоритм деления многочленов, находим такие многочлены что

Операция алгоритма деления (с остатком) для многочленов несколько сложнее, чем для чисел. В любом случае имеются делимое и делитель d и требуется найти частное и остаток (В алгоритме Евклида ) При этом должно выполняться условие Для построения многочленов применяем итерацию. Начинаем с Если то полагаем

Ясно, что Процедура заканчивается, когда Далее полагаем

Так как многочлен не зависит от то он равен как и требуется.

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

В алгоритме Евклида для многочленов возникает последовательность остатков, степени которых строго убывают. Значит, для некоторого Далее

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

Этот метод обладает тем же серьезным недостатком — он требует чрезвычайно большого объема памяти для запоминания

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

и

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

Так как то, очевидно,

Из алгоритма Евклида вытекает несколько следствий. Во-первых, ясно, что любой общий делитель многочленов должен также делить следовательно, любой общий делитель делит Это доказывает, что наибольший общий делитель многочленов и Во-вторых, ясно, что два н. о. д. этих многочленов должны делить друг друга. В числовой области отсюда сразу следует единственность н. о. д. с точностью до знака. Для многочленов над полем отсюда вытекает, что н. о. д. двух многочленов определяется с точностью до скалярных множителей — элементов поля Эту неоднозначность можно устранить с помощью задания н. о. д. в виде нормированного многочлена со старшим коэффициентом, равным 1. Тогда можно утверждать, что любые два многочлена над имеют единственный нормированный н. о. д. (исключается случай двух нулевых многочленов). Многочлен (ненулевой степени), не имеющий делителей, кроме скаляров и скалярных кратных самого себя, называется неприводимым. Используя алгоритм Евклида, легко показать, что если неприводимый многочлен делит произведение многочленов то делит либо либо Действительно, если не делит то и тогда Значит,

Так как делит оба члена в левой части этого равенства, то он

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

2.14. Теорема. Любой нормированный многочлен над полем однозначно записывается в виде произведения нормированных неприводимых многочленов над

Этот результат справедлив для любого поля Аналогом теоремы 2.14 для целых чисел является утверждение о том, что любое натуральное число, не равное 1, однозначно представимо — в виде произведения простых сомножителей.

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

2.15. Теорема. Многочлен степени d над полем в любом поле, содержащем имеет не более d корней.

Заметим, что теорема 2.15 неверна для многочленов с коэффициентами из кольца 2). Например, квадратный многочлен имеет четыре корня в кольце классов вычетов по модулю 15, а именно

Такая ситуация, как правило, имеет место для составных модулей. Если простые, произвольные положительные числа, то сравнение эквивалентно системе сравнений

Таким образом, сравнение эквивалентно паре сравнений каждое из которых имеет точно два решения. Следовательно, в результате имеются четыре решения: с любой комбинацией знаков. -

В общем случае решения сравнений по составному модулю описываются следующими утверждениями:

2.16. Китайская теорема об остатках для чисел. Для заданных простых чисел и произвольных чисел система сравнений имеет единственное решение по модулю

2.17. Китайская теорема об остатках для многочленов. Для заданных неприводимых многочленов и произвольных многочленов система сравнений однозначно разрешима относительно по модулю

Доказательство (для многочленов). Так как многочлен не имеет с нетривиальных общих делителей, то, используя алгоритм Евклида, можно найти такой многочлен что Положим далее Очевидно, для всех при этом выполняется сравнение Если также является решением этой системы уравнений, то делится на для всех к, так что

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

Следствия из алгоритма Евклида для многочленов в основном аналогичны следствиям из алгоритма Евклида для чисел. Однако в деталях эти следствия существенно различны. Несмотря на это имеется один важный частный случай, в котором возможно построение прямого соответствия.

2.18. Теорема. Если число чисел то над любым полем многочлен является н. о. д. многочленов

Доказательство. Запишем формулу геометрической прогрессии

Полагая и умножая на получаем, что

Таким образом, шагу алгоритма деления для чисел соответствует равенство

Следовательно, остаток от деления на для всех А и алгоритм Евклида для многочленов строится в прямом соответствии с алгоритмом Евклида для чисел. При получаем Многочлен, полученный на предпоследнем шаге алгоритма, является н. о. д. исходных многочленов

Теоремы 2.14-2.18 очень важны, однако польза от варианта непрерывных дробей алгоритма Евклида не ограничивается этими теоретическими результатами. Он составляет также основу технической реализации одной из арифметических операций (деления), необходимых для декодирования БЧХ-кодов. Перейдем к рассмотрению этой реализации.