У. Питерсон - Коды, исправляющие ошибки (1267328), страница 39
Текст из файла (страница 39)
Ч. т. д. Теорема 6.27. Все корни неприводилого многочлена имеют один и тот иге порядок. Доказательство. По теореме 6.26, если р — один нз корней многочлена, то любой из остальных корней может быть. представлея 7 / в виде рч при некотором 1. Пусть е — порядок (1, а е — порядок ('ч. Тогда (()т) ~ ч~ (6е)а~ 1ч' и поэтому е делится на е'. Аналогично ~ =Ь"")'=6'" "=1Ь")'Т" =1 "'=1, так что е' делится на е. Поскольку е и е' — целые положительные числа, то е' = е. Ч.
т. д. Порядок корней неприводимого многочлена называется показателем, которому этот многочлен принадлежит. Если пепрнводимый многочлен принадлежит показателю е, то он является дели- гелем многочлена Х' — 1, но не нвляется делителем многочленов вида Х" — 1 при и ~ г. Неприводимый многочлеп степени и над полем 6Р(д) называется примитивным, если его корнем является примитивный элемент поля 6Р(д ). Тогда этот корень и„ следовательно, все корни имеют порядок д — 1, и по теореме 6.27 все они †примитивн элементы. Неприводимый многочлен степени и> является примитивным тогда и только тогда, когда он принадлежит показателю д'" — 1. Наконец, неприводимый многочлен степени >и является примитивным тогда и только тогда, когда он не является делителем многочлена Х" — 1 ни при каких и, меньших чем д — 1.
6.7. Структура конечных полей. Резюме Содержание теорем из предыдущего раздела иллюстрируется в этом разделе разложением на множители многочлена Хзз — 1 над полем 6Р(2). Те >ке идеи применимы и к более общей задаче разложения на множители многочлена Х" — 1 над полем 6Р(д), если корни многочлена Х" — 1 принадлежат 6Р(ц ). Тщательное изучение и полное понимание идей, представленных в этом разделе, окажутся очень полезными для понимания теории циклических кодов. Все ненулевые элементы поля 6Р(64) могут быть представлены как степени некоторого примитивного элемента а.
Итак, этими элементами являются О, 1, а, аз, аз, ... „азз и Хзз — 1=(Х вЂ” 1)(Х вЂ” а)(Х вЂ” а') ... (Х вЂ” азт). (6.9) Далее, так как (аз')' = азз = 1, то порядок элемента ам равен 3. Тот же самый порядок имеет элемент а'з. Аналогично (аз)т = а", так что порядок элемента а' равен 7, и таков же порядок элементов а'з, аз>, азз, азз и азз. Порядок элементов аг, а", азз, азз, азз н азз равен 9. Заметим, что (аз')з= 1, но порядок элемента аз' равен 3, а не 9, поскольку порядок элемента 6 равен наименьшему в, такому, что 6'= 1. Аналогично любая степень а, показатель которой делится на 3, но не делится на 7 или на 9, является элементом порядка 21.
Таких элементов 12. Остальные 36 элементов должны иметь порядок 63. Определим теперь круговой многочлгн Фз(Х)=(Х вЂ” 61)(Х вЂ” рз) ... (Х вЂ” р,), где рь рз, ..., р,— набор всех элементов порядка 1. Тогда зр~ = Х вЂ” 1 згз= (Х вЂ” аз') (Х— — "), ),=(Х- з)(Х- ')(Х- )(Х- )(Х- )(Х- -) " т. д Кроме того, равенство (6.9) может быть записано в виде 1= т1 (Х)>Рз(Х)>Р>(Х)МЪ(Х) з)з1 (Х)з)>м(Х). (6 1О) Корнями многочлена Хз' — 1 являются все элементы р, для которых яз1 = 1, и поэтому этот многочлен содержит в качестве множителей >РФ(Х) для всех 1, на которые делится 21. Таким образом, Хм — 1 = ~)м (Х)~ут(Х)~~(Х)~)~(Х), и аналогично Хз 1 гз (Х) ~гз (Х) г1 (Х) Х' — 1 = % (ХМ (Х), Хз — 1 = Фз (ХИ, (Х), Х вЂ” 1=Ф(Х).
(6.11) Этн равенства могут быть переписаны в виде Ф(Х)=Х вЂ” 1 ч'3 (Х) ( хг — ! Ф(Х)= р, !х) х9 — ! Ф (х)~Рз!Х) х" — ! ч'21 ( ) ) (х) ~) (х) ч (х) хбз ~, (х) ~, (х) ~, (х) з,„(х) з„(х) (степень (степень (степень (степень (степень (степень 1), 2), 6), (6.12) 6), 12), 36). Степень ~);(Х) совпадает с числом элементов порядка 1, которое уже было вычислено. Кроме того, степень многочлена ~)ь очевидно, равна 1.
Степень ~~, равна разности между степенью Хз — 1 и степенью знаменателя ~,(Х) и т. д. По теореме 6.25 элементы порядка 3 должны обладать минимальными многочленами над ОР(2) степени 2, поскольку они являются элементами 6Р(2з). Это значит, что многочлен ~уз(Х) не- приводим над бг" (2з). Действительно, ненулевыми элементами 6Р(2з) являются корни многочлена Хз — 1, т. е. 1, сР н сг'з.
Ана. логично элементы порядка 7 принадлежат бр(2') и обладают минимальными многочленами степени 3, поэтому многочлен $г(Х) должен разлагаться на два непрнводимых многочлепа степени 3. Все остальные элементы бг" (2з) не являются элементами какого- либо подполя, и, следовательно, все их минимальные многочлены являются многочленами степени 6. Кроме того, заметим, что поскольку все корни неприводимого многочлена имеют один и тот же порядок (теорема 6.27), то, если один из корней неприводимого многочлена р(Х) имеет порядок 1, все его корни имеют порядок ! н являются, следовательно, корнями ~;(Х). В этом случае ~,(Х) делится на р(Х).
Таким образом, многочлен ~уз(Х) должен быть непрнводнмым. й!ногочлен фм(Х) должен иметь два множителя степени 6, а многочлен ~)м(Х) должен иметь шесть множителей степени 6. теплица зин Рввложение на множители миогочленв Хээ — 1 Х вЂ” ! = )ь(Х) )з(Х)6т(Х) )э(Х)6ьь(Х) )вз(Х) ,цх) - х — ! ь(ьэ(х) = тм(Х) тзь(Х) = (Х вЂ” аз') (Х аьз) ь)ьэ(Х) = то(Х)тз (Х) тз(Х) = (Х вЂ” ао) (Х аьв) (Х азв) тм(Х) (Х вЂ” аз') (Х вЂ” аэь) (Х аьв) )о(Х) = тз(Х) тз( ) = (Х вЂ” а )(Х аьь) (Х азз) (Х вЂ” вв ь(ьэь(Х) = тз(Х)т,в(Х) ( — а ) ( — а ) (Х вЂ” а'з) (Х вЂ” азе) (Х вЂ” аьз) (Х вЂ” зз) тьз(И)=(Х вЂ” аьВ(Х аз)(Х аз, (Х эВ И,( ь)ьвз(Х) = то(Х)тв(Х)тьь(Х)тьз(Х)тзэ(Х)тзь(Х) ьоь(Х) (Х вЂ” а) (Х вЂ” а') (Х вЂ” аь) (Х вЂ” ав) (Х вЂ” а") (Х вЂ” а") т (Х) (И ав) (Х аьо) (Х аэо) (Х аоо) (Х ьзьь) (Х аэь) тьь(Х) = (Х вЂ” ам) (Х вЂ” ам) (Х вЂ” а'ь) (Х вЂ” ам) (Х аэо) (Х вЂ” ььзь) т,з(Х) = (Х вЂ” а")Г,И вЂ” азв) (Х вЂ” а") (Х вЂ” а") (Х вЂ” а'э) (Х вЂ” аэз) тзз(Х) = (И вЂ” азз) (Х вЂ” а"в) (Х вЂ” а'з) (Х вЂ” а*з) (Х вЂ” а'з) (Х вЂ” аоз) глэ,(Х) = (Х азь) (Х азз) (Х вЂ” аоь) (Х вЂ” аээ) (Х вЂ” аэз) (Х вЂ” аьь) Теперь можно сделать еще один шаг.
Если р — корень неприводимого многочлена р(Х), то его остальные корни равны рв, ))в, Рв, Рьв и ()м. Обозначим через тг(Х) минимальный многочлен для а*'. Тогда т, (Х) = (Х вЂ” а) (Х вЂ” ав) (Х вЂ” ав) (Х вЂ” ав) (Х вЂ” а'е) (Х вЂ” ааз), тв (Х) = (Х вЂ” ав) (Х вЂ” ае) (Х вЂ” аьз) (Х вЂ” авв) (Х вЂ” авз) (Х вЂ” ам) ! т.д. Заметим, что (азв) в = аов = а'в поскольку а"' = 1. Кроме гого, заметим, что (а'з) з = авв = а, поскольку ам = 1, н, таким збразом, процесс последовательного возведения в квадрат порожаает только шесть различных корней многочлена тг(Х). Анало.ично (азв) ' = аве = а'. далее, (ао) ' = а", (а") ' = авз и (а") ' = = атз = ав, и, таким образом, последовательное возведение в свадрат дает только три различных корня мпогочлена тэ(Х). Это .огласуется с тем фактом, что степень многочлена тз(Х) должна быть равна 3, так как все элементы порядка 9 принадлежат ьгг (2з) .
Все эти результаты сведены в табл. 6.2. Определим двойственный многочлен 1*(Х) для 1(Х) как с 1(1/Х), где т — степень 1(Х). (В качестве коэффициентов мно'очлена 1*(Х) берутся коэффициенты многочлена )(Х), но в обзатном порядке.) Несколько фактов относительно двойственных взгогочленов сформулированы в задаче 6.7. В рассматриваемом зпучае, ввиду того что порядки элементов () и 6-ь совпадают, если корень многочлена ьрв(Х), то р ' — тоже корень этого много- члена.
Отсюда вытекает, что многочлен ф;(Х) является двойственным самому себе. В частности, это так для т~(Х). Оба многочлена чч(Х) и фм(Х) являются произведениями двух неприводимых многочленов, так что либо каждый из сомножителей должен быть двойственным самому себе, либо один из сомножителей должен быть двойственен другому; для ф,(Х) и фм(Х) имеет место второй случай. (Однако, например, многочлен яхт(Х) является произведением двух неприводнмых многочленов степени 8, каждый из которых является двойственным самому себе.) Никакой примитивный многочлеи не может быть двойственным самому себе (задача 6.7), и поэтому среди шести сомножителей, составляющих многочлен фм(Х), должны содержаться три пары двойственных многочленов. Так как а-' =ам — корень глз,(Х), то гпя(Х)=и,(Х).
Так как а ~=а — корень гл (Х), то гл, (Х) =т,(Х). Так как а "=и'" — корень т„(Х), то и, (Х)=тп (Х). Все это можно получить, не обращаясь к явным выражениям для многочленов. Разложение на множители может быть завершено прямым вычислением, как это было сделано прн составлении приложения В; для многочленов небольших степеней над 6Р(2) разложение на множители может быть завершено на основе приложения В или таблиц Марша. 8.8.
Векторные подпространства и линейные преобразования конечных полей Пусть 1(Х) — многочлен с коэффициентами из 6Р(д ) следующего вида: Г 1(Х) = ~ а,Х~ . (8.13) В соответствии с теоремой 6.14 он задает линейное преобразование в себя поля 6Р(д ), рассматриваемого как векторное пространство над 6Р(д). Так как преобразование является линейным, то и совокупность корней, и совокупность возможных значений являются подпространствами пространства 6Р(д ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
