С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 3
Текст из файла (страница 3)
+ апхпв случае ао = О необратимы) .10.Многочлены от одного неизвестного х с действительными коэффициентами относительно обычных операций?1. 3. (IIIпоток) Группы, кольца, поляКольцо (многочлены ао + а1х + а2х252+ ... + anxnв случае а 0 == О необратимы) .Зада чаf :11.6.---+ 21,Р ешен и е .ХотяJ(xy)лиНет!+у) == 2(х +у) == 2х== 2ху i= (2х) · (2у) == f(x)1.7.Р е ш е ни е.отображепие== 2х гомоморфизмом 'К;ОЛе'Ц?J(xЗада чавf (х)Явл.яетс.яЯвл.яетс.я ли полеНет !z2 : 1 + 1 == о ,а в+ 2у == J(x) + J(y),но· f(y) .12подполем пол.я15?z5 - 1 + 1 == 2,т.
е . операция сложения вZ5к своему подмножеству {О ,неустойчива при переходе1}.26ГлаваГлава2.Конечные поля2Конечные поляПоля вычетов2.1• 1 -кольцо целых чисел евклидово, возможно деление с остатком.•р-• (р)простое число .=== { nрn Е1}=== р 1 === { О , ±р,± 2р , . . . } -идеал, порождённый числом р.• 1/(р)===1jp1==={о ,I, ... , р- 1} -вычетов по модулто этого идеала===кольцоклассы остатков от деления на р :-о:=:1:=:-• • •р- 1о + (р) '1 + (р) '=?• • • • • •:=:1 === OU 1U ... Up- 1.p- l +(p)Черту над символами классов вычетов часто не ставят.Поскольку р - простое , то 1/(р) - не просто кольцо , а поле, и в нём возможно деление без остатка налюбой неиулевой элемент.Это rк;оне'ч,rное поле, точнее простое поле Галуа, обозначение -modр.lrpилиGF(p) ; всеоперации в нём-по2.1.
(IIIпоток) Конечные поляПримеры: поле27IF3 == 7L/ (3) и фактор-кольцо 7L/ (4) -+ 11о 11 12 1IFзо:ох 11 о 11 12 11 2о1 22 1о1оо12о2+ 11о 11 12 13 1ооох 11 о 11 12 13 11 2 3ооооо1 1 2 3о1о1 2 3о123о2 о 23 2 123Во1 1 227L/(4):о2 33 о1 2о7L/(4) дважды два равно нулю !Однако поле из4 элементов существует...Характеристика поля.п оле,1-Пусть!k -произвольноеего единица.Складываем единицы:1 == 1 , 1 + 1 == 2 , ....В конечном поле всегда найдётся первое1 + ...\..,v+1,.1kтакое , что== о.kразТогдаk-порядок; аддитuв?-tой группrы пол.я== харак;теристик;а поляЕсли все сумм ы вида1 + ..
.+ 1lk ,!k ==символич ескиchar !k.различны, то полагаютchar !k == О (а не оо ;) ) .Q, IR -поля нулевой характеристики .{0, 1, 2, ... , char !k- 1} -минимальное подполе поля !k.28ГлаваПример2.12.Конечные поля(Бесконечное поле с положительной характеристикой). Пусть1. [k [x] -[k - некоторое поле . Построим :'К;ОЛЪ'ЦО .мnогоrчлеnов (от формальной переменной х) над полем[k:{ Р(х) ~ ао + а1х + ... + anxn ао, . .. , an Е [k};[k [х] Н { ( ао , . .
. , an) Е [kn 1 n Е rN о } .2. [k(x)-поле рациональных функций над[k; в нём:#О) , гдеэлементыР,-"дроби"Р/ Q (еслиQQ Е [k[x];умножение-(P/Q)эквивалентностьеслисложениеP1Q2--~·(И /V) ~P1/Q1P2Q1;~(PU)j(QV);P2/Q2 ,дроби можно приводить к общемуз наменателю и складывать :P/Q + U/Vвключение-~(PV + QU)j(QV);поскольку[k[x] С [k(x), то каждыймногочлен Р отождествляется с Р /1.Если в качестве [k взять [FP, то lrp(x)- бесконечное поле положительной характеристики р.~2.1 (тождество Фробениуса, силь н ое у проще ни евычислений в конечном п оле). В поле хара'К;теристu'К;uр>О въlnoлneno тождество2.1 .
(IIIпоток) Конечные поля29Доказа тельство . В любом коммутативном кольце вернаформула для бинома(а+ Ь)Р==аР + С~аР- Ь + ...1+ с:-11аьР- +ьР,=0а п ри.с;-.==ipl1, . . . , р -1 числитель коэффициентаi!(p~i)! делится на р, а знаменатель-нет, отку-да с; -р О.оСле ствие. В поле харагк;теристигк;и р(аnn>О справедливоn+ Ь )Р == аР + ьР .Мультипликативная группа и примитинный элемент конечного поля.п=-;==[ГР""' { О} - .мулътиплигк;ативна.я группа пол.я [Гр·Утве ж ениеп=-;2.1.группа пор.ядгк;а р-чигк;личесrк;а.я по умножению- 1.Как любая конечная циклическая группа ,жит генератор•==примитивный элемент а:любой элементf3Е п=-; является некоторой егонатуральной степенью :• причём 1 == аР- 1 и•rr; содерп=-; имеет ср(рaif3 ==ai,i Е { 1, ...
, р- 1};=1- 1 для 1 ~ i ~ р - 2.- 1) примитивных элементов .Рассмотрим поле [Г 11 . Его мультипликативная груп-па естьср( 1 0)lri 1== 41-rv( {1, 2 . . . , 10} , х)примитивных элемента .не генератор, проверяем2:и она имеетГлава30k1 2 3 42 4 8 52kт.е .-7 8 9 107 3 6 1== 10.ord 21 2 3 4 53 9 5 4 13kord 3Конечные поля3:kт. е .610 9генератор [F! 1 ,2-П роверяем-52.== 5ине генератор, и т.д.3-Как ускорить процесс?Если примарное разложение р- 1известно =} элемент а Е [FР примитивен-ар-1qф.Р 1 для каждого простого(т.к.
akoгda== 1, kЕiffq (р - 1)!N).Пример: 1) р == 11 (наш случай), р- 1 == 10 == 2 · 5,qЕ {120 ==25252 == 4 =/= 1, 2 == 325'150 ==113 == 9 =/= 1, 3 == 243 -2}10 =/= 1111=}=}3- не примитивный.2) р == 37, р- 1 == 36 == 2 · 3 . Находим : ~ == 18,== 12; поэтому для выяснения, является ли а Е [F;23632 - примитивный,2генератором, нужно проверить не более двух равенств:а12== 1 и а18== 1.- неизвестно =} эффективного алгоритма не найдено;используют таблицы, вероятностные алгоритмы ...Однако , если найден один примитивный элемент аполя [Fр, то любой другой его примитивный элемент может быть получен как степень ak, где k - взаимно просто с р-1.поток) Конечные поля2.1 .
(IIIПример (наш): р3111 , 2 - примитивный элемент lГ 11k Е { 1, 3, 7, 9 } - взаимно простые с 10, получим12т. е .6, 73==22==128и8-7==2'==1 1==8'92 == 5127,==116,также примитивные элементы [Г 11 .Заметим, чтоОi-а Е [ГР ==? аР- 1==1 ==? аР- 2Например , найдём обратный элемент к4-111 2==== 4 -Действительно,94 == 2621443 · 4 11 1.==k[x]над полемk-а- 1 .в п оле lГ 1 1 :23831. 11 + 3Деление в кольце многочленов.членов4==-113.Кольцо многоевклидово , - значит многочлены можно делить друг на друга с остатком .42Например, поделим <<уголком >> х на х + 1 в кольцеZ2[x] :т.
е .х4Самостоятельно : делением многочленов « уголком »покажите, что частное от деления многочлена 2х +х4 + 4х + 3 на многочлен 3х 2 + 1 в кольце [Г 5 [х] есть234х + 2х + 2х + 1, а остаток- 2х + 2.5Пример2.2. В кольцеf(x)7==42разделимZ2[x]х +х +х +1 на g(x)==многочленх 3 +х+ 1 с остатком:32Глава 2. Конечные полях7+ х5+х4х5x 2+ l+х5 +хз+х2х3 +х3 + х1+lхИтак , f(x) === g(x)(x4+ х + 1) + х .2Веприводимые многочлены .Кольцо многочленовlk [х] над полем lk - евклидово {::} оно факториального{::} каждый его элемент однозначно с точностьюдоперестановакразлагаетсявпроизведениепростых(неразложимых).Простые (неразложимые) элементы колец lk [x] называют uеприводи.мы.ми .мuогочлена.ми, они не имеютнетривиальных делителей.Свойство << неприводимости >> зависит от поля: многочлен х 4IF2 [х] :+ 1 неприводим в над ~[х], но приводим надх + 1 === ( х + х + х + 1) · (х + 1).432Вопросы для кольца многочленов над данным полем:1)какие многочлены неприводимы?2) как их находить?Неприводимые многочлены над С,IRи~:поле С-только многочлены 1- й степени;поле IR- 1) многочлены 1- й степени,- 2) многочлены 2-й степени с отрицательнымдискриминантом;п оле ~-существуют неприводимые многочлен ыпроизвольной степени.2.1 .
(III поток) Конечные поля33Далее нас будут интересовать неприводимые (и чаще- нормированные) многочлены в конечных полях.Ясно, что количество нормированных многочленовстепениxnnнад полемIFРвида-+ a n _ 1xn- l + ... + а1х + ао,ai Е1Fp, i=O,n -1- равно рп .Неприводимые многочлены кольца IF 2 [x] . Найдём вIF 2 [х] все веприводимые многочлены степеней 2, . . .
, 5.Вторая степень : х + ах + Ь.2Ясно , что Ь = 1, иначе х + ах = х(х + а) =? ищем2веприводимый многочлен в виде х + ах + 1.22Если а= О, то х + 1 = (х + 1) ;а= 1, то получаем единственный веприводимый2многочлен степени 2 над IF 2 :х + х + 1.2Третья степень: х3+ ах + Ьх + 1.2(почему свободный член не равен нулiо?)Исключая , как сделано ранее, делимость на хполучаем условие а+ Ьт.е.а=ОЬ=1а=Ь =Следовательно надмых многочленаi= О,'1,+ 1,'О.IF 2 существуетстепени 3:два веприводиГлава34Четвёртая степень: хИсключение делимостиа+ Ь + с == 1, т. е .4+ ах + Ьх + сх + 1.на х + 1 приводит к услови1оимеется3Конечные поля2.42варианта, которые да1от3решения:ьасмногочлен1 х41 о х44о о х1 1 х4ооо11+х+12+х +13+х +123+х +х +х+1-приводимыйН айдены многочлены, у которых нет линейных делителей.
Но м ногочлен 4-й степени может разлагаться впроизведение двух н еприв одимых многочленов 2-й степ ени :Пятая степень : хИсключение5432+ ах + Ьх + сх + dx + 1.делимости на х + 1 приводит квию : число иенулевых коэффициентов а, Ь , с,но быть нечётным, т.е . либо1, либо 3, чтодолжdдаётусло8мноделимостьнагочленов.Далеенеобходимомногчленымногочленов2-йиисключить3-йстепени,2-й степени один ,ноа3-йнеприводимых-два,и их••произведение дает два мно гочле на.Итого : существует6неприводимых многочленовй степени. Для справки: вот оних52+ х + 1,253х + х + х + х + 1,453х + х + х + х + 1,х53+ х + 1,542х + х + х + х + 1,4253х + х + х + х + 1.5-2.1 . (III поток) Конечные поля35Веприводимые многочлены из lrз[x] .Многочлены степени1:х+ 1х2х2хх+2+12х+ 2Какие из них неприводимы? Все! (шутка) .Вот неприводимые многочлены степени(они не имеют корней О ,х2х22х + 22х2х + 2х + 2члены вn1, 2) :2+1+х+2Для всех ли р и2 в lrз [x]2+х+122х + 2х + 1существуют неприводимые многоlrР?Тео ема2.
1 (о су щест вова нии н е при водимых мн о гоч л ен ов). Дл.я любых простого р и 'Натуралъ'Ного n в lrр [х]существует 'Неnриводимъtu М'Ногочле'Н стеnе'Ни-n.докажем позже.Итак, в кольцахlrp [x]есть неприводимые многочленылr-обой степени, но как их найти?Ответ: нет эффективных алгоритмов (из таблиц, алгоритм Берлекэмпа ... )Зачем нужны неприводимые многочлены?С помощью неприводимых многочленов можно строитьновые конечные поля1.-расшире'Ни.я простых полейВ ыбираем простое р- q)иксируем полеlrР :lrp .2. Рассматриваем кольцо lrp[x] многочленов над lrp.36Глава3.Выбираем натуральное2. Конечные поляи неприводимый мноnгочлена (х)==4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
