Главная > Помехоустойчивое кодирование > Коды, исправляющие ошибки
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.6. Мультипликативная группа поля Галуа

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

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

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

Теорема 6.18. Многочлен имеет своими корнями все ненулевых элементов поля

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

Теорема 6.19. Многочлен делится на многочлен тогда и только тогда, когда делится на

Доказательство. Предположим, что Тогда делится на поскольку корень многочлена Подставляя получаем, что делится на

Теперь допустим, что где Тогда

и в соответствии с алгоритмом деления

Сравнивая эти равенства, находим, что

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

Теорема 6.20. В поле существует примитивный элемент а, т. е. элемент порядка Каждый ненулевой элемент поля может быть представлен как некоторая степень а, т. е. мультипликативная группа поля Ралуа нвляется циклической.

Доказательство этой теоремы будет опущено. Доказательства ее можно найти, например, в книгах [1] (стр. 124) и 134]. Обоснованность этой теоремы можно увидеть на основе следующих приблизительных рассуждений. Элемент порядка должен быть корнем многочлена и поскольку должен быть делителем то многочлен должен быть делителем Но делителей многочлена вида при просто недостаточно для того, чтобы соответствовать всем ненулевым элементам поля. Поэтому должен существовать некоторый элемент поля а, который является корнем многочлена но не является корнем никакого многочлена при следовательно, порядок а должен быть равен Тогда различных элементов поля все являются корнями многочлена так что эта совокупность должна быть совокупностью всех ненулевых элементов поля.

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

Таблица 6.1 (см. скан) Представление поля

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

Теорема 6.21. Если многочлен с коэффициентами из поля и корень в расширении поля то также является корнем

Доказательство. Пусть Тогда

по теореме 6.14. Далее, по теореме и поэтому а для любого элемента а из Следовательно, и если то

Теорема 6.22. Рассмотрим расширение поля которое содержит все корни многочлена Тогда совокупность этих корней является подполем.

Доказательство. Если а и корни многочлена, то также корень многочлена так как по теореме Кроме того, и, таким образом, — а есть корень этого многочлена, если а является его корнем. (Заметим, что , если характеристика поля равна 2.) Поэтому корни многочлена образуют аддитивную группу. Если а и корни многочлена, то произведение также его корни (если Остальные аксиомы удовлетворяются благодаря тому факту, что корни принадлежат полю. Ч. т. д.

Теорема 6.23. Каждый многочлен степени неприводимый над полем является делителем многочлена

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

Теорема 6.24, Каждый делитель многочлена неприводимый над полем имеет степень, равную или меньше.

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

По теореме следовательно, для любого элемента а из поля и поскольку принадлежат следовательно, принадлежат также расширению поля то

Но а — корень многочлена и поэтому для всех Таким образом,

т. е. также корень многочлена Так как имеется таких элементов, в то время как имеет не более чем корней, то следовательно, Ч. т. д.

Теорема 6.25. Если элемент расширения поля то порядок элемента является делителем но не является делителем никакого меньшего числа вида ; здесь — степень минимальной функции для

Доказательство. Пусть минимальная функция для (3; предположим, что ее степень равна Тогда является делителем многочлена по теореме является корнем многочлена Поэтому порядок является делителем Предположим, что делится на порядок при Тогда является корнем многочлена является делителем по теореме 6.16. Таким образом, степень многочлена по теореме 6.24 не превосходит

Теорема 6.26. Пусть многочлен степени с коэффициентами из поля который неприводим в этом поле, и пусть корень многочлена в расширении поля. Тогда все корни многочлена

Доказательство. По теореме 6.21 элементы являются корнями многочлена Следующее рассуждение

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

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

Теорема 6.27. Все корни неприводимого многочлена имеют один и тот же порядок.

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

и поэтому делится на Аналогично

так что делится на Поскольку целые положительные числа, то

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

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

Пример. Рассмотрим процесс разложения на множители многочлена над полем Этот многочлен полностью разлагается на

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

Тогда

и каждый из множителей является многочленом.

Ненулевые элементы поля Галуа по теореме 6.20 могут быть все представлены как степени примитивного элемента а, порядок которого равен 63. Легко проверить, что элемент I является корнем многочлена Элементы имеют порядок 3 и должны обращать в нуль многочлен Элементы имеют порядок 7 и являются поэтому корнями многочлена Элементы являются корнями многочлена Элементы имеют порядок 9 и являются корнями в то время как остальные элементы являются корнями многочленов и Аналогично степени элемента а, показатели которых кратны 3, но не кратны 9 или 21, являются элементами порядка 21 и поэтому корнями многочлена Корни все имеют порядок, равный 63, и, следовательно, примитивны. Многочлены называются круговыми многочленами. Разложение многочлена на круговые многочлены может быть проведено над любым полем.

По теореме 6.25 для элемента порядка 3 должны существовать минимальные многочлены для этих элементов степени 2. Этот результат подтверждается, Корни порядка 7 должны иметь минимальные функции степени 3, и поэтому многочлен должен быть произведением двух кубических многочленов. Так как по теореме 6.25 все остальные многочлены должны иметь степень 6, то многочлен неприводим и принадлежит показателю 9, многочлен (X) содержит два неприводимых множителя, которые принадлежат показателю 21, и многочлен содержит 6 неприводимых множителей, которые принадлежат показателю 63 и потому примитивны.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление