Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 31
Текст из файла (страница 31)
Тогда :--1=(х — Н("4-:+х фх+ П =Е,йфф.(х). Пуси и = 5. Тогда х' — 1=-(х — 1)(х-1-1)(х"-1-» ! 1)РН -х 1 1)— = а, (х) О. (х) Е. (х) Г), (х). Пусть л = 7. Тогла х' — 1 .= (х — 1) (х' -1- х' -~- х' -г- х' ф х' ф х ф 1) = =О,() Е,() Пусть н = 8.
Тогда 3 1 = (, !) (х + 1) (з + 1) (хг ф 1) = = Е, ( ) О, ( ) О.( ) О. « Пусть л = й. Тагла з ! =[х 1)(хз, х+1)(хг.(-хаф 1) = = О, (х) О. (х) Е. (х). Общий случай описывается следующей теоремой. Теорема 5.5.2. Дгя каждого л бей й„(х) =: й (и), где й (л) — функция Эйггро. Доюжатггьспмо, ф (и) определяется как число целых чисел, меньших л и взаимно простых с и, и зто в точности совпадает с числомлниейных множителей, входящих в определение Г)„(х) П Теарена 5.5.3. Дгя «аждоео и х" — 1 = П Оь(х).
б.з Пр ив эле гас Гя.б.торячявл мгоэ В а !З7 Доказательства. Непосредственные вычисления дают. к" — 1- П(х-и'.)=.П П (х — и'„)= — и иана, !- и = Пф„(х) Теорема 5.5зй Дод лроныогвкыл комм коэффицнеллш кругавога многое вно всегол «вяяются целыми этого ловя. Доюшатеяьство.
Воспользуемся индунцией по л. Коэффициенты мвогочлена !)т (х) = х — 1 являкггся целыми. Согласна теореме 5.5.3, () (х)= П ПЕ.(1 г! е< Деление приведенного многочлена с целыми коэффициентами на приведенный мнагочлен с целнчи коэффициентами дает в зиле шстного приведенный многочлен с целыми каэффициеатами. Следовательно, утверждение теоремы верно для любого л, если оно верна длн всех меньших положительных целых л.
П Теорема 6.5.6. Дед повем рацнаюзязяых чисел все крдговыг много«мни являюякя простылч и, следовательно, линимагьныли лнагачяеколи дяя соответствующих варлей иа единицы. Доказательство. Приведенность круговык многочленав оче. видна. Доказать надо только неприводимость круговых многочле. нов над полем рациональных чисел. Пусть /(х) обозначает мини.
мальный многочлеи элемента о„ нэд полем рапнанальных чисел. Пусть й — произвольное целое число, взаимно простое с л, н пусть й(х) — минимальный миогочлен элемента ю, над полем рациональных чисел. Предположим, чта й (х) = /(х) для каждого такого й. Тогда многочлен /(х) должен быть «ратным много- члену !г„(х). н так как !3,(х) приведен и имеет рациональные коэффидиенты, 1(х) .= 1)„ (х). Тогда наша задача сводится к до. казательству тога, чта для каждого взаимно простого с л числа й минимальный многочлен д(х) элемента и, равен мноючлену /(х). Шог 1. Докажем саачала это утверждение юя случая, «агда й равно простому числу р, не являющемуся делителем л.
Пусть й (х) — минимальный многачлен элемента и,' и предположим, чта ои не равен мнаючлену /(к). Тогда к' — 1 =- / (х) й (к) 1 (к) для некотпрого многочлеяа 1(х), коэффициенты «отарого целые числа, так «ак оба многочлеиа / [х) и й (х) янляются делителями ' миогочлена х' — 1 и имеют целые коэффициенты. Таи как зле. мент ю„ является корнем многачлена б (хг), то многочлеи й (хэ) кратен многочлену /(х): й (хэ) = / (х) й (х) для некоюрого много«лена й (х) с целымн коэффициентами. За- меним теперь оба равенства вычетами па модулю р: х — 1 = / (х) й (х) 1 гх) (шоб р), й(х') =-/(х) й(х) (шоб р). Согласно теореме 2.2.4, второе равенство записывается в виде (й (х))в == / (х) й (х) (шоб р). Рассмотрим разложение этога уравнения над полем СР (р) Каж- дый простой делитель р (х) мншочлена / (х) лалжсн быть простым делителем многачлена (д (х))", и, следовательно, многачлека й (х) Следовательно, (х" — 1) должен делиться иа (р (х))' Но тогда формальная производная лх"-' ат нногочлена (х" — 1) делится над,би (р) на р (х), Но оредпаложению р не делит л, а х не ыожег быть делителем / (х)(пюб р), так как / (х) делит х" — 1.
Палу- ~еянае противоречие показывает, чта К (х) не может быть не рав. аым / (х). Шт 2. Теперь докажем утверждение дл» произвольного й, вааимна простота с л. Запишем разложение й на простые множи. тели: р р» Каждмй из этих множителей взаимно прост с и. так как й взаимно просто с я Сагласао утверждению шага 1, если и„— корень мнагочлена / (х), та и' таиже является корнем зтога мвогачлена. Теперь опять воспользуемся шагам 1: если и„'' — корень многа- члена /(х), то и юг'" является «орнем этого иаагачленв Испольаун ицдукцню.
получаем, что и ы„ является парнем /(х). П 5.5. Примитивные алименты Согласно данному в разд. 2.3 опрелечеиню, примитивным эле. мегпоч поля Галуа называе.ся такой звемеит и, что каждый ненулевой элемент поля можно однозначно записать в виде стеаени этого элемента Например, в псле 6Р (7) выполняются равевства 3' = 3, 3' -. †. 2, 3* = 6, 3' = 4, 3' = 5, 3' =. 1, так чта 3 является примитивным элементом паля бу (7).
Примитивные элементы полезны нрн тктроеиин полей, так иак, коль скоро адни из них найден, то, перемножая степени этого примитивного элемента, можно построить таблицу умножения в игом пале. В палих Галуа !зо примитивные влемеиты играют роль основания логарифмов В даяном разделе будет доказано, что кажлпе «овечвсе поле со. держит нрямитивный элемент Костяное поле образует абелсву группу двояким способом, Множество всех элементов поля образует абелеоу группу по ело.
женню, н множество всех элеьгентов поля, исключая нуль, абра. зуст збелсву группу пп умножению.Мы булем работать с группой по умножению. Согласно теореме 2.1.5, порндак этой группы делится ва порядок каждого ес элемента. Тспрема 5.6.1. 1уусть Оо Ом ., (1,, — нснулсамс элементы поля ОР (й); тогда: х' ' — ! --.(х — йт)(х — 5) (х — Ос-т). Доказательство, Множество ненулевых элементов поля ОР (д) образует конечную группу по уьтожеиню Пусть 6 — канай. лггбо элемент из ОР (О), и пусть й — мультипликативный парялок эт го зл мев а.
Тот, согласно теореме 2.1.5, й делит о — 1. Слелавательво, $ (Оь)м ~)сз !м — мгтс так что 5 нвляетсн корнем мкагочлепа х" — 1 (з Т орема 5,6.2. Группа нгяугсоых элгмгнтоз поля ОР (д) по умножению лгопгтсл диягииской. Докоэатгльстзо. Если число д — 1 простое, то теорема трави. альна, ибо норядок всех элементов, за исключением аула и едипины, равен у -- 1, так что каждый такой элемевт примитивен. Доказывать теорему надо только для составного числа д — 1.
Рассмотрим разложение числа у — 1 нв простые множители: П р)п — 1 Так как ОР (у) — поле, то орели ега д — 1 ненулевых элементов должен нвйтась хотя бы один, не являюжийся корнем многочлена хы "" — 1, поскольку этот многочлен может иметь «е более (у — 1МР, корней Счсдавательно, двя каждого 1 можно найти !с-~ног со-п(о,'с такай элемента, поля ОР (у), что а! 'чь 1.
Пусть Ьг - ас и пусть Ь == П Ь,. Покажеы, по порядок Ь равен д — 1, и, . следовательно, группа является циклической. (Дог 1 Порядок злеыента Ьс равен р,д Доююатсльстзо, с)о идно, что Ь, .= 1, тан что порядок Ь, дет~!т рс' Он ра. в.н числу инда рсд Если л, ментис го то Ь,' = 1 Но ! -г!)с, = о, чь 1, и. следовательно, порядок элемента Ь! равен р! . ! (уог 2. Порядок элемента Ь равен д — 1. Докозаомлостго. Прсжюложим, что Ь" =- 1. Покажем сначала, то вз этого вы. т ьж"т рзвенство л .= О (ют) р,') для всск г =- 1, „з. Для жгого с можно записать ( ° П )т) |свив Ь на Ц Ьс и используя равенство Ь)' - 1, находим ( П о)т) ннам образом, л !)Рог=О (!падр,'), Поскотьку р, представляют собой разгтчные простые числа, то О (тод р,') для каждого(.
Сле!овательчо, и -=О (моду 1). 1 ортга доказана. С, Теорема 5.6.3. В назсдои поли Галуа амгстся примлтитмд ы ~снос. Дот!ттг.гостов. Так кзк ненулевые элементы поля ОР (у) »оазуют дяклаческую группу, то среди ннх имеется элсмеггг порядка д — 1. Этот элемент является примитивным П Задача о() — 1 1 о() — — * 1- "1 с.(-!, )99 Гл 6. Тмр и . л влт брв р поп«й 3 м . и Д )(ОД (Р, (*), Р.
(")! под (о, !.), р, (.)) = д (*) р, (*) -р в ( ) р. ( ). 6.9. Пут м,()= '-(- -)- ),,(л) — *'-!. (, Н(л) =*' — !. ( б,(4), с,()=с(л) (моб,(*)), *" — ! — (л — !) Р (*), р н ( ай (*) Р = Р Рб *(*) .Р т (л) т' (л), л л 6.9. и л повн бр((П' в. Сл Р Р д онвптр до н мо! ОР Пбд 6.(! П .тр п п л бу(У), д б ми !в л кс нупнмв. 6,(6. Д, т и о» *'.(- -(- ! ынрввом в д р л о . и мп. Замлчанмд Глина б ВЫЧИСЛЕНИЯ В СУРРОГАТНЫХ ПОЛЯХ Часто задачу вычисления в заданном поле можно нложитз в друюе поле, произвести там необходимые вычисления, а затем ответ вернуть в звланнае поле Целесоабразнссть такого перехода может мотивироватьсз различными причинами Может оказатьс», что в павам поле необходимые вычисления выполнить легче, и это уменьшает объем работ или упрощает реализацию вычислений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
