Конечные поля (часть 1) (1127160), страница 9
Текст из файла (страница 9)
. . , β p :¶ âñå ðàçëè÷íû; · èñ÷åðïûâàþò ñïèñîê âñåõ n êîðíåé f (x)(èõ íàçûâàþò ñìåæíûìè).Ò.å. ÷òîáû ïîëó÷èòü âñå êîðíè íåïðèâîäèìîãî ìíîãî÷ëåíà,äîñòàòî÷íî íàéòè îäèí èç íèõ è âîçâîäèòü åãî ïîñëåäîâàòåëüíî âñòåïåíèp.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà77 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Ñëåäóþùàÿ òåîðåìà ïîçâîëÿåò ðàñêëàäûâàòü ìíîãî÷ëåíû íàìíîæèòåëè.Òåîðåìà (ñâîéñòâî êîðíåé íåïðèâîäèìîãî ìíîãî÷ëåíà)Ïóñòü β êîðåíü íåïðèâîäèìîãî ìíîãî÷ëåíà f (x) ñòåïåíè n ñ2n−1êîýôôèöèåíòàìè èç Fp .
Òîãäà ýëåìåíòû β, β p , β p , . . . , β p :¶ âñå ðàçëè÷íû; · èñ÷åðïûâàþò ñïèñîê âñåõ n êîðíåé f (x)(èõ íàçûâàþò ñìåæíûìè).Ò.å. ÷òîáû ïîëó÷èòü âñå êîðíè íåïðèâîäèìîãî ìíîãî÷ëåíà,äîñòàòî÷íî íàéòè îäèí èç íèõ è âîçâîäèòü åãî ïîñëåäîâàòåëüíî âñòåïåíèp.Äîêàçàòåëüñòâî¶ Ïîêàæåì, ÷òî åñëè β êîðåíü f (x), òî β p òîæå êîðåíü.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà78 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...Ïîñêîëüêó ap = a äëÿ âñåõ a ∈ Fp , òî ñïðàâåäëèâîa0 + a1 x + .
. . + ak xkp= ap0 + ap1 xp + ap2 x2p + . . . + apk xkp == a0 + a1 (xp ) + a2 (xp )2 + . . . + ak (xp )k ,ò.å. äëÿ ëþáîãî ìíîãî÷ëåíà ϕ(x) ∈ Fp [x] âûïîëíÿåòñÿ ðàâåíñòâîp(∗)ϕ(x) = ϕ(xp ).Îòñþäà:f (β) = 0 ⇔ f (β)p = 0 ⇔ f (β p ) = 0è β, β p , . . . , β pn−1 êîðíè ìíîãî÷ëåíà f (x).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà79 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû íàä êîíå÷íûì ïîëåì...n−1· Îñòàëîñü äîêàçàòü, ÷òî âñå β, β p , .
. . , β pðàçëè÷íû, èòîãäà (ìíîãî÷ëåí ñòåïåíè n èìååò íå áîëåå n êîðíåé) ìîæíîóòâåðæäàòü, ÷òî íàéäåíû âñå êîðíè ìíîãî÷ëåíà f (x).lkÏðåäïîëîæèì, ÷òî β p = β p è áåç îãðàíè÷åíèÿ îáùíîñòèl < k . Èìååì:n1βp = β;2ïîñêîëüêónk ·pn−kβp = βp=kβppn−kòî β êîðåíü óðàâíåíèÿ xp=n−k+l −1βplpn−kn−k+l= βp,− 1 = 0.Èç òåîðåìû ¾Âñå íåïðèâîäèìûå ìíîãî÷ëåíû n-é ñòåïåíè íàäFp ÿâëÿþòñÿ äåëèòåëÿìè xpn − x¿ ïîëó÷àåìn − k + l > n ⇒ l > k ïðîòèâîðå÷èå.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà80 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèé ¾íåïðèâîäèìûé ìíîãî÷ëåí = 0¿Ïðèìåðû1. Íàéòè êîðíè íåïðèâîäèìîãî íàäF2f (x) = x4 + x3 + 1ìíîãî÷ëåíàÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà80 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèé ¾íåïðèâîäèìûé ìíîãî÷ëåí = 0¿Ïðèìåðû1. Íàéòè êîðíè íåïðèâîäèìîãî íàäF2ìíîãî÷ëåíàf (x) = x4 + x3 + 1Ðåøåíèå. Îäèí êîðåíü ïîëó÷àåì íåìåäëåííî:x(èëèx).Ïî òîëüêî ÷òî äîêàçàííîé òåîðåìå ìîæíî âûïèñàòü îñòàëüíûåêîðíè â ïîëåx2 ,F2 [x]/(f (x)):x4 = x3 + 1,x8 = x6 + 1 = x3 + x2 + x.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà80 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèé ¾íåïðèâîäèìûé ìíîãî÷ëåí = 0¿Ïðèìåðû1.
Íàéòè êîðíè íåïðèâîäèìîãî íàäF2ìíîãî÷ëåíàf (x) = x4 + x3 + 1Ðåøåíèå. Îäèí êîðåíü ïîëó÷àåì íåìåäëåííî:x(èëèx).Ïî òîëüêî ÷òî äîêàçàííîé òåîðåìå ìîæíî âûïèñàòü îñòàëüíûåêîðíè â ïîëåx2 ,F2 [x]/(f (x)):x4 = x3 + 1,x8 = x6 + 1 = x3 + x2 + x.x2 äåéñòâèòåëüíî êîðåíü f (x):f (x2 ) = x4 + x3 + 1x 7→ x2 = x4·2 + x4+2 + 1x4 7→ x3 +1 =Ïîêàæåì, ÷òî, íàïðèìåð,= (x3 + 1)2 + (x3 + 1)x2 + 1 = x6 + 6 1 + x5 + x2 + 6 1 == x6 + x5 + x2 = x2 (x4 + x3 + 1) = x2 · 0 = 0.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà81 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèé ¾íåïðèâîäèìûé ìíîãî÷ëåí = 0¿Ïðèìåðû2. Ðåøèòü óðàâíåíèåf (x) = x4 + x3 + x2 + x + 1 = 0,f (x) ∈ F2 [x].Ðåøåíèå.f (x) íåïðèâîäèì â F2 [x].Ïîýòîìó îäèí åãî êîðåíü x, è ïî äîêàçàííîé òåîðåìåâûïèñûâàåì îñòàëüíûå â ïîëå F2 [x]/(f (x)):Óáåæäàåìñÿ, ÷òî ìíîãî÷ëåíx2 , x4 = x3 + x2 + x + 1, x8 = x6 + x4 + x2 + 1 = . . . = x3 .Ïîêàæèòå ñàìîñòîÿòåëüíî, ÷òîf (x),x3 äåéñòâèòåëüíî êîðåíüò.å. ÷òîf (x3 ) = x12 + x9 + x6 + x3 + 1 = 0.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèÿ ¾íåïðèâîäèìûé ìíîãî÷ëåí = 0¿Ïðèìåðû3. Ðåøèòü óðàâíåíèåf (x) = x2 + 2x − 1 = 0,ãäåf (x) ∈ F3 [x].82 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà82 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèÿ ¾íåïðèâîäèìûé ìíîãî÷ëåí = 0¿Ïðèìåðû3. Ðåøèòü óðàâíåíèåf (x) = x2 + 2x − 1 = 0,Ðåøåíèå. Ïåðåáîðîì ýëåìåíòîâóáåæäàåìñÿf (x)Íî òîãäà â ïîëåÏîñêîëüêóF3 [x]/2x + 12f (x) ∈ F3 [x].x ∈ F3 = { 0, 1, 2 } íåïðèâîäèìûé ìíîãî÷ëåí.x2 + 2x + 2x2 = −2x + 1 = x + 1,Óáåäèìñÿ, ÷òîãäå êîðåíüîí èìååò êîðíèòîxèx3 .x3 = x2 + x = 2x + 1.f (x):2f (x + x) = (2x + 1) + x + 2 − 1 == x2 + x + 1 + x + 1 = 3 · (x + 1) = 0.Îòâåò: óðàâíåíèåèìååò êîðíèxèf (x) = x2 + 2x − 1 = 0, ãäå f (x) ∈ F3 [x]2x + 1 â ïîëå F3 [x]/ x2 + 2x + 2 .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà83 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèÿ ¾íåïðèâîäèìûé ìíîãî÷ëåí = 0¿...ÏðèìåðûÏðîâåðèì, êñòàòè, ÿâëÿåòñÿ ëè íåïðèâîäèìûé ìíîãî÷ëåíf (x) = x2 + 2x + 2 ∈ F3 [x]ïðèìèòèâíûì?F2 ñîñòîèò èç 833ýëåìåíòîâ, 8 = 2 èìååò åäèíñòâåííûé ïðîñòîé äåëèòåëü 2 è84ïîýòîìó íåîáõîäèìî ïðîâåðèòü ðàâåíñòâî x = 1 ( = 4).22Èìååì ( x = x + 1 ):Ìóëüòèïëèêàòèâíàÿ ãðóïïà ïîñòðîåííîãî ïîëÿx4 = x22= (x + 1)2 = x2 + 2x + 1 =6 x + 1+ 6 2x + 1 = 2 6= 1.Ýòî îçíà÷àåò, ÷òîïðèìèòèâíûé.deg x = 8è äàííûé ìíîãî÷ëåí ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà84 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÊàê ðåøàòü óðàâíåíèÿ f (x) = 0, êîãäà êîðíåé íåò?Àëãîðèòì íàõîæäåíèÿ âñåõ êîðíåé ïîëèíîìà f (x) ∈ Fp[x]1Ðàçëîæèòü2Äëÿ êàæäîãî ìíîãî÷ëåíàðàñøèðåíèåni = deg gif (x) íà íåïðèâîäèìûå ñîìíîæèòåëèf (x) = g1 (x) · g2 (x) · .
. . · gk (x).gi (x), i = 1, kíàäFp [x]:ðàññìîòðåòüFp [x]/(gi (x)), â êîòîðîì îí áóäåò èìåòüêîðíåé2α, αp , αp , . . . , αpni −1.Çàïèñàòü äàííûå êîðíè êàê ìíîãî÷ëåíû èç ïîëÿFp [x]/(gi (x)).3Îáúåäèíèòü âñå êîðíè â îäíîì îáùåì ðàñøèðåíèèãäån =HOK ( n1 , . . . ,nk ).Fnp ,ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà85 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèÿÇàäà÷àf (x) = 2x4 + x3 + 4x2 + 4 = 0íàä.
Ðåøèòü óðàâíåíèåf (x) = 2x4 + x3 + 4x2 + 4 = 0,ãäåf (x) ∈ F5 [x].F5ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà85 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèÿÇàäà÷àf (x) = 2x4 + x3 + 4x2 + 4 = 0íàäF5. Ðåøèòü óðàâíåíèåf (x) = 2x4 + x3 + 4x2 + 4 = 0,ãäåf (x) ∈ F5 [x].Ðåøåíèå. Âû÷èñëÿåì çíà÷åíèÿ f (x) äëÿx ∈ F5 = { 0, 1, 2, 3, 4 }: f (0) = 4, f (1) = 1, f (2) = 0.Òàêèì îáðàçîì, x = 2 êîðåíü f (x).Äåëÿ ¾óãîëêîì¿2x4+x3+f (x)4x2íàf1 (x) = x − 2 (= x + 3),+ 4 = (x − 2) ·(2x3ïîëó÷èì+ 4x + 3).2x3 + 4x + 3 : ò.ê. 2−1 = 3,2x3 + 4x + 3 = 0 áóäåì ðåøàòü óðàâíåíèåÄëÿ óäîáñòâà íîðìèðóåì ÷àñòíîåâìåñòî óðàâíåíèÿf2 (x) = 3 · (2x3 + 4x + 3) = x3 + 2x + 4 = 0.òîÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà86 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèÿÏåðåáîðîì ýëåìåíòîâf (x) = 2x4 + x3 + 4x2 + 4 = 0x ∈ F5íàä F5...f (0) = 4, f (1) = 2, f (2) = 1, f (3) = 2, f (4) = 1óáåæäàåìñÿ, ÷òîf2 (x) = x3 + 2x + 4 íåïðèâîäèìûéìíîãî÷ëåí (à åñëè áû ýòî áûë ìíîãî÷ëåí ïîëåáóäóòF5 [x]/x,x5 ,x3+ 2x + 44-éñòåïåíè?).êîðíÿìè ìíîãî÷ëåíàf2 (x) = 0x25 .Âû÷èñëÿåì ñ ó÷¼òîìx3 = −2x − 4 = 3x + 1:x5 = x2 (3x + 1) = 3x3 + x2 = 4x + 3 + x2 = x2 + 4x + 3.55x25 = x5 = x2 + 4x + 3 = x10 + 45 x5 + 35 == x10 + 4(x2 + 4x + 3) + 3 = x10 + 4x2 + x.(ïîñêîëüêó45 = 210 = 1024Íàéä¼ì îòäåëüíîx10 .è35 = 81 · 3 = 243).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà87 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐåøåíèå óðàâíåíèÿx10 = x52f (x) = 2x4 + x3 + 4x2 + 4 = 0= x2 + 4x + 32íàä F5...= x4 +x2 +32 +3x3 +4x+x2 == x4 + 3x3 + 2x2 + 4x + 4 = 36 x2 + 6 x+ 6 4x + 3+ 6 2x2 + 4x + 4 == 4x + 2.Ïðîäîëæàåì:x25 = x10 + 4x2 + x = 6 4x + 2 + 4x2 + 6 x = 4x2 + 2.Îòâåòf (x) = 2x4 + x3 + 4x2 + 4 = 0, ãäå22f (x) ∈ F5 [x] èìååò êîðíè 2, x, x + 4x + 3, 4x + 2 â ïîëå3F = F5 [x]/ x + 2x + 4 (ïîñêîëüêó êîðåíü 2 ∈ F ).: óðàâíåíèåÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà88 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÎ ïîðîæäàþùåì ìíîãî÷ëåíåx3 + 2x + 4 ∈ F5 [x]Êñòàòè, ÿâëÿåòñÿ ëè íåïðèâîäèìûé âa(x) = x3 + 2x + 4ïðèìèòèâíûì?F5 [x]ìíîãî÷ëåíÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà88 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÎ ïîðîæäàþùåì ìíîãî÷ëåíåx3 + 2x + 4 ∈ F5 [x]Êñòàòè, ÿâëÿåòñÿ ëè íåïðèâîäèìûé âa(x) = x3 + 2x + 4F5 [x]ìíîãî÷ëåíïðèìèòèâíûì?Ìóëüòèïëèêàòèâíàÿ ãðóïïà ïîñòðîåííîãî ïîëÿ53− 1 = 124äëÿd=124 = 22 · 31,= 62 è d =1242x,ðàâåíñòâî12431äëÿ êîòîðîãîxd = 1íóæíî ïðîâåðèòü= 4.x62 = (x31 )2 = (x25 · x6 )2 .63 2 = (3x + 1)2 = 4x2 + x + 1,Ïîñêîëüêó x = xxx3 = 3x + 1.x4 = x3 x = 3x2 + x 6= 1.Âû÷èñëÿåì:31ñîñòîèò èçýëåìåíòîâ.Îïðåäåëèì ïîðÿäîê å¼ ýëåìåíòàÏîñêîëüêóF352243òî2= (4x +2)·(4x +x+1) = x +4x +4x +3x2 +2x+2 == x4 +4x3 +2x2 +2x + 2 = 3x2 + x + 2x + 4 + 2x2 + 2x + 2 = 1deg x = 31è ìíîãî÷ëåía(x)íå ïðèìèòèâåí.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
