Конечные поля (часть 1) (1127160), страница 3
Текст из файла (страница 3)
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà20 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÑóùåñòâîâàíèå è íàõîæäåíèå íåïðèâîäèìûõ ìíîãî÷ëåíîâÒåîðåìà (î ñóùåñòâîâàíèè íåïðèâîäèìûõ ìíîãî÷ëåíîâ)Äëÿ ëþáûõ íàòóðàëüíîãî n è ïðîñòîãî p íàäíåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n.FpñóùåñòâóåòÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà20 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÑóùåñòâîâàíèå è íàõîæäåíèå íåïðèâîäèìûõ ìíîãî÷ëåíîâÒåîðåìà (î ñóùåñòâîâàíèè íåïðèâîäèìûõ ìíîãî÷ëåíîâ)Äëÿ ëþáûõ íàòóðàëüíîãî n è ïðîñòîãî p íàäíåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n. äîêàæåì ïîçæå.FpñóùåñòâóåòÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà20 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÑóùåñòâîâàíèå è íàõîæäåíèå íåïðèâîäèìûõ ìíîãî÷ëåíîâÒåîðåìà (î ñóùåñòâîâàíèè íåïðèâîäèìûõ ìíîãî÷ëåíîâ)Äëÿ ëþáûõ íàòóðàëüíîãî n è ïðîñòîãî p íàäíåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n.Fpñóùåñòâóåò äîêàæåì ïîçæå.ÂîïðîñÊàê â êîëüöåFp [x]íàéòè íåïðèâîäèìûé ìíîãî÷ëåí?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà20 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÑóùåñòâîâàíèå è íàõîæäåíèå íåïðèâîäèìûõ ìíîãî÷ëåíîâÒåîðåìà (î ñóùåñòâîâàíèè íåïðèâîäèìûõ ìíîãî÷ëåíîâ)Äëÿ ëþáûõ íàòóðàëüíîãî n è ïðîñòîãî p íàäíåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n.Fpñóùåñòâóåò äîêàæåì ïîçæå.ÂîïðîñÊàê â êîëüöåÎòâåòFp [x]íàéòè íåïðèâîäèìûé ìíîãî÷ëåí?: íåò ýôôåêòèâíûõ àëãîðèòìîâÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà20 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÑóùåñòâîâàíèå è íàõîæäåíèå íåïðèâîäèìûõ ìíîãî÷ëåíîâÒåîðåìà (î ñóùåñòâîâàíèè íåïðèâîäèìûõ ìíîãî÷ëåíîâ)Äëÿ ëþáûõ íàòóðàëüíîãî n è ïðîñòîãî p íàäíåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n.Fpñóùåñòâóåò äîêàæåì ïîçæå.ÂîïðîñÊàê â êîëüöåÎòâåòFp [x]íàéòè íåïðèâîäèìûé ìíîãî÷ëåí?: íåò ýôôåêòèâíûõ àëãîðèòìîâ(èç òàáëèö, àëãîðèòì èç5-éãëàâû ¾Àëãåáðû¿ Âàí äåðÂàðäåíà, àëãîðèòì Áåðëåêýìïà...)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà20 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÑóùåñòâîâàíèå è íàõîæäåíèå íåïðèâîäèìûõ ìíîãî÷ëåíîâÒåîðåìà (î ñóùåñòâîâàíèè íåïðèâîäèìûõ ìíîãî÷ëåíîâ)Äëÿ ëþáûõ íàòóðàëüíîãî n è ïðîñòîãî p íàäíåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n.Fpñóùåñòâóåò äîêàæåì ïîçæå.ÂîïðîñÊàê â êîëüöåÎòâåòFp [x]íàéòè íåïðèâîäèìûé ìíîãî÷ëåí?: íåò ýôôåêòèâíûõ àëãîðèòìîâ(èç òàáëèö, àëãîðèòì èç5-éãëàâû ¾Àëãåáðû¿ Âàí äåðÂàðäåíà, àëãîðèòì Áåðëåêýìïà...)Åñëè ìíîãî÷ëåí íå èìååò êîðíåé, ýòî åù¼ íå çíà÷èò, ÷òî îííåïðèâîäèì. Ïî÷åìó?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÇà÷åì íóæíû íåïðèâîäèìûå ìíîãî÷ëåíû?21 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà21 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÇà÷åì íóæíû íåïðèâîäèìûå ìíîãî÷ëåíû?Èñïîëüçóÿ íåïðèâîäèìûå ìíîãî÷ëåíû, ìîæíî ñòðîèòü íîâûåêîíå÷íûå ïîëÿ ðàñøèðåíèÿïðîñòûõ ïîëåéFpÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà21 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÇà÷åì íóæíû íåïðèâîäèìûå ìíîãî÷ëåíû?Èñïîëüçóÿ íåïðèâîäèìûå ìíîãî÷ëåíû, ìîæíî ñòðîèòü íîâûåðàñøèðåíèÿêîíå÷íûå ïîëÿ 1Âûáèðàåì ïðîñòîå2Ðàññìàòðèâàåì êîëüöî3Âûáèðàåì íàòóðàëüíîåFpÈäåàë(a(x))Fp :p è ôèêñèðóåì ïîëå= h { 0, 1, .
. . , p − 1}, +p , ·p i.a(x) = an4ïðîñòûõ ïîëåéxnFp [x]ìíîãî÷ëåíîâ íàäFp .n è íåïðèâîäèìûé ìíîãî÷ëåí+ . . . + a1 x + a0 ∈ Fp [x].Fp [x]/(a(x)),r(x) ìíîãî÷ëåíîâ,r(x):ïîðîæäàåò ôàêòîðêîëüöîýëåìåíòû êîòîðîãî ñóòü ñîâîêóïíîñòèäàþùèõ ïðè äåëåíèè íàa(x)îñòàòîêr(x) = { f (x) ∈ Fp [x] | f (x) = a(x) · q(x) + r(x) } .ÓòâåðæäåíèånÌíîæåñòâîr(x)oÿâëÿåòñÿ ïîëåì Ãàëóà GF (pn ).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ðàñøèðåíèé ïðîñòûõ êîíå÷íûõ ïîëåéÄîêàçàòåëüñòâî12Êîëüöî ìíîãî÷ëåíîâo åâêëèäîâî, èäåàë (a(x)) n Fp [x]ìàêñèìàëüíûé ⇒ r(x) ïîëå.noÅãî ìîùíîñòü r(x) = ÷èñëî ìíîãî÷ëåíîâ íàä Fpñòåïåíè íå âûøå n − 1, ò.å. |{r(x)}| = pn .22 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà22 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ðàñøèðåíèé ïðîñòûõ êîíå÷íûõ ïîëåéÄîêàçàòåëüñòâî12Êîëüöî ìíîãî÷ëåíîâo åâêëèäîâî, èäåàë (a(x)) n Fp [x]ìàêñèìàëüíûé ⇒ r(x) ïîëå.noÅãî ìîùíîñòü r(x) = ÷èñëî ìíîãî÷ëåíîâ íàä Fpñòåïåíè íå âûøå n − 1, ò.å. |{r(x)}| = pn .noÏîëår(x) = GF (pn ) íàçûâàåòñÿ ðàñøèðåíèåì n-éñòåïåíè ïðîñòîãî ïîëÿ Fp ; àëüòåðíàòèâíîå îáîçíà÷åíèå ÂîïðîñFnp .Ïî÷åìó â îáîçíà÷åíèè Fnp íå èñïîëüçóåòñÿ ìíîãî÷ëåí a(x), ñïîìîùüþ êîòîðîãî ïîñòðîåíî ïîëå?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà22 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ðàñøèðåíèé ïðîñòûõ êîíå÷íûõ ïîëåéÄîêàçàòåëüñòâî12Êîëüöî ìíîãî÷ëåíîâo åâêëèäîâî, èäåàë (a(x)) n Fp [x]ìàêñèìàëüíûé ⇒ r(x) ïîëå.noÅãî ìîùíîñòü r(x) = ÷èñëî ìíîãî÷ëåíîâ íàä Fpñòåïåíè íå âûøå n − 1, ò.å. |{r(x)}| = pn .noÏîëår(x) = GF (pn ) íàçûâàåòñÿ ðàñøèðåíèåì n-éñòåïåíè ïðîñòîãî ïîëÿ Fp ; àëüòåðíàòèâíîå îáîçíà÷åíèå ÂîïðîñFnp .Ïî÷åìó â îáîçíà÷åíèè Fnp íå èñïîëüçóåòñÿ ìíîãî÷ëåí a(x), ñïîìîùüþ êîòîðîãî ïîñòðîåíî ïîëå?ÒåîðåìàËþáîå êîíå÷íîå ïîëå èçîìîðôíî êàêîìó-íèáóäü ïîëþ ÃàëóàFnp .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà23 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏðèìåð: ïîñòðîåíèå ïîëÿ F23Âûáåðåì âx2 + 1 .F23∼=F3 [x] íåïðèâîäèìûé ìíîãî÷ëåí: ïóñòü ýòî áóäåòÒîãäà èñêîìîå ïîëå åñòüF3 [x]/x2 + 1 == 0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2 .Ìîæíî ñîñòàâèòü òàáëèöû ñëîæåíèÿ è óìíîæåíèÿ â ýòîì ïîëåñ ó÷¼òîìx2 = −1 ≡3 2.Íàïðèìåð:x · 2x = 1,x + 1 + x + 2 = 2x,2x + 1 · x = x + 1,2x + 1 + x = 1,è ò.ä.×åðòó íàä ýëåìåíòàìè ïîëÿFp [x]/(a(x))íàçûâàþò èõ ¾ìíîãî÷ëåíàìè¿...îáû÷íî íå ñòàâÿò èÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëÿ F23...Çàìåòèì, ÷òî(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.24 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà24 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëÿ F23...Çàìåòèì, ÷òî(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Ýòî çíà÷èò, ÷òî(àxx+1 ïðèìèòèâíûé ýëåìåíò ïîëÿ4 íåò, ïîñêîëüêó x= 4 ≡3 1).F23ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà24 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëÿ F23...Çàìåòèì, ÷òî(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Ýòî çíà÷èò, ÷òî(àxx+1 ïðèìèòèâíûé ýëåìåíò ïîëÿ4 íåò, ïîñêîëüêó xÂîïðîñF23= 4 ≡3 1).×òî áóäåò, åñëè ïðè ïîñòðîåíèè ïîëÿ âìåñòî x2 + 1 âçÿòüäðóãîé íåïðèâîäèìûé â F3 [x] ìíîãî÷ëåí?Íàïðèìåð, 2x2 + x + 1?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà24 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëÿ F23...Çàìåòèì, ÷òî(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Ýòî çíà÷èò, ÷òî(àxx+1 ïðèìèòèâíûé ýëåìåíò ïîëÿ4 íåò, ïîñêîëüêó xÂîïðîñF23= 4 ≡3 1).×òî áóäåò, åñëè ïðè ïîñòðîåíèè ïîëÿ âìåñòî x2 + 1 âçÿòüäðóãîé íåïðèâîäèìûé â F3 [x] ìíîãî÷ëåí?Íàïðèìåð, 2x2 + x + 1?Îòâåò: ïîëó÷èòñÿ ïîëå, èçîìîðôíîå ïîñòðîåííîìó.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà25 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂû÷èñëåíèÿ â êîíå÷íîì ïîëå: ïðèìåðÇàäà÷à. Îïåðåäèòü, ÿâëÿåòñÿ ëè:1. Ìíîãî÷ëåía(x) = x3 + 2x + 4 ∈ F5 [x]22. Ýëåìåíò 4x + 2 êîðíåì35 [x]/ x + 2x + 4 ?Fa(x) íåïðèâîäèìûì?â ôàêòîðêîëüöå/ïîëåÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà25 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂû÷èñëåíèÿ â êîíå÷íîì ïîëå: ïðèìåðÇàäà÷à.
Îïåðåäèòü, ÿâëÿåòñÿ ëè:1. Ìíîãî÷ëåía(x) = x3 + 2x + 4 ∈ F5 [x]22. Ýëåìåíò 4x + 2 êîðíåì35 [x]/ x + 2x + 4 ?FÐåøåíèåa(x) íåïðèâîäèìûì?â ôàêòîðêîëüöå/ïîëå.1. Ïåðåáîðîì ýëåìåíòîâx ∈ GF (5) = { 0, 1, 2, 3, 4 }a(0) = 4, f (1) = 2, a(2) = 1, a(3) = 2, a(4) = 1óáåæäàåìñÿa(x) íåïðèâîäèìûé ìíîãî÷ëåí4-é ñòåïåíè?).F = F5 [x]/ x3 + 2x + 4x3 = −2x − 4 = 3x + 1.(à åñëè áû ýòî áûë ìíîãî÷ëåíÑëåäîâàòåëüíî, ôàêòîðêîëüöîÿâëÿåòñÿ ïîëåì è â í¼ìÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà25 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂû÷èñëåíèÿ â êîíå÷íîì ïîëå: ïðèìåðÇàäà÷à. Îïåðåäèòü, ÿâëÿåòñÿ ëè:1.
Ìíîãî÷ëåía(x) = x3 + 2x + 4 ∈ F5 [x]22. Ýëåìåíò 4x + 2 êîðíåì35 [x]/ x + 2x + 4 ?FÐåøåíèåa(x) íåïðèâîäèìûì?â ôàêòîðêîëüöå/ïîëå.1. Ïåðåáîðîì ýëåìåíòîâx ∈ GF (5) = { 0, 1, 2, 3, 4 }a(0) = 4, f (1) = 2, a(2) = 1, a(3) = 2, a(4) = 1óáåæäàåìñÿa(x) íåïðèâîäèìûé ìíîãî÷ëåí4-é ñòåïåíè?).F = F5 [x]/ x3 + 2x + 43ÿâëÿåòñÿ ïîëåì è â í¼ì x = −2x − 4 = 3x + 1.3222. a(4x + 1) = 2(2x + 2)+ 2 · 2(2x2 + 1) + 4 =6422= 3(3x + 2x + x + 1) + 3x + 3 = 4x6 + x4 + x2 + 1 == 4(3x+1)2 +3x2 +x+x2 +1 = x2 +4x+4+3x2 +x+x2 +1 = 0.(à åñëè áû ýòî áûë ìíîãî÷ëåíÑëåäîâàòåëüíî, ôàêòîðêîëüöîÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
