Конечные поля (часть 1) (1127160), страница 2
Текст из файла (страница 2)
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà9 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏðèìåð: ìóëüòèïëèêàòèâíàÿ ãðóïïà ïîëÿ F11F∗11= { 1, 2, . . . , 10 },¶F∗11÷èñëî ãåíåðàòîðîâ ∼= h { 1, 2 . . . , 10 }, ×11 ih1i = { 1 },h2i = { 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 },(210 = 1024 ≡11 = 1) . . .h3i = { 3, 9, 5, 4, 1 }åù¼ ãåíåðàòîðû:·F∗11ϕ(10) = 4.6, 7, 8∼= h { 0, 1, . . . , 9 }, +10 i:h0i = { 0 },h2i = { 2, 4, 6, 8, 0 }åù¼ ãåíåðàòîðû:h1i = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 },...3, 7, 9ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿ Fp?Åñëè ïðèìàðíîå ðàçëîæåíèåp−110 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà10 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿ Fp?Åñëè ïðèìàðíîå ðàçëîæåíèå1) èçâåñòíî ýëåìåíòα(ò.ê.p−1q6≡p 1p−1α ∈ Fpïðèìèòèâåí iäëÿ êàæäîãî ïðîñòîãîαk deg α = 1, k ∈ N).q | (p − 1)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà10 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿ Fp?Åñëè ïðèìàðíîå ðàçëîæåíèå1) èçâåñòíî ýëåìåíòα(ò.ê.p−1q6≡p 1p−1α ∈ Fpïðèìèòèâåí iäëÿ êàæäîãî ïðîñòîãîq | (p − 1)αk deg α = 1, k ∈ N).Ïðèìåð:p = 11, p − 1 = 10 = 2 · 5, q ∈ {2, 5}22 = 4, 25 = 32 ≡11 10 ⇒ 2253 = 9, 3 = 243 ≡11 1 ⇒ 3 ïðèìèòèâíûé íå ïðèìèòèâíûéÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà10 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿ Fp?Åñëè ïðèìàðíîå ðàçëîæåíèå1) èçâåñòíî ýëåìåíòα(ò.ê.p−1q6≡p 1p−1α ∈ Fpïðèìèòèâåí iäëÿ êàæäîãî ïðîñòîãîq | (p − 1)αk deg α = 1, k ∈ N).Ïðèìåð:p = 11, p − 1 = 10 = 2 · 5, q ∈ {2, 5}22 = 4, 25 = 32 ≡11 10 ⇒ 2253 = 9, 3 = 243 ≡11 1 ⇒ 3 ïðèìèòèâíûé íå ïðèìèòèâíûé2) íåèçâåñòíî ýôôåêòèâíîãî àëãîðèòìà íå íàéäåíî(èñïîëüçóþò òàáëèöû, âåðîÿòíîñòíûå àëãîðèòìû...).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà11 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿ Fp...Åñëè íàéäåí îäèí ïðèìèòèâíûé ýëåìåíòαïîëÿFp , òî ëþáîéäðóãîé åãî ïðèìèòèâíûé ýëåìåíò ìîæåò áûòü ïîëó÷åí êàêñòåïåíüαk ,ãäåk âçàèìíî ïðîñòî ñp − 1.Ïðèìåð: p = 11, 2 ïðèìèòèâíûé ýëåìåíò F11k ∈ { 1, 3, 7, 9 } âçàèìíî ïðîñòûå ñ p − 1 = 1021 = 2,23 = 8,27 = 128 ≡11 7,29 = 512 ≡11 6.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà12 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè îáðàòíûé ê ýëåìåíòó FpÏóñòü0 6= α ∈ Fp .Èìååìαp−1 = 1 ⇒ αp−2 = α−1 .ÏðèìåðÍàéä¼ì îáðàòíûé ýëåìåíò ê4Ïðîâåðêà:−1= 47−24â ïîëå510= 4 = 2F7 := 1024 ≡7 2.4 · 2 = 8 ≡7 1.Î÷åâèäíî, ìåòîä óäîáåí ïðè íåáîëüøèõ çíà÷åíèÿõp.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà13 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÄåëåíèå ñ îñòàòêîì â êîëüöå ìíîãî÷ëåíîâ íàä ïîëåìÓòâåðæäåíèåÊîëüöî ìíîãî÷ëåíîâ k[x] íàä ïîëåì k åâêëèäîâî. çíà÷èò, ìíîãî÷ëåíû ìîæíî äåëèòü äðóã íà äðóãà ñ îñòàòêîì.Íàïðèìåð, ïîäåëèì ¾óãîëêîì¿x4íàx2 + 1ò.å.â êîëüöåF2 [x]:x4 = (x2 + 1)2 + 1.Óïðàæíåíèå: äåëåíèåì ìíîãî÷ëåíîâ ¾óãîëêîì¿ ïîêàæèòå, ÷òî2x5 + x4 + 4x + 3 íàF5 [x] åñòü 4x3 + 2x2 + 2x + 1,÷àñòíîå îò äåëåíèÿ ìíîãî÷ëåíàìíîãî÷ëåíîñòàòîê 3x2 + 12x + 2.â êîëüöåàÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà14 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíûÒåîðåìàÊàæäûé ýëåìåíò åâêëèäîâà êîëüöà îäíîçíà÷íî ñ òî÷íîñòüþ äîïåðåñòàíîâîê ðàçëàãàåòñÿ â ïðîèçâåäåíèå ïðîñòûõ ýëåìåíòîâ.Ïðîñòûå (íåðàçëîæèìûå) ýëåìåíòû êîëåöñïåöèàëüíîå íàçâàíèå k[x]èìåþòíåïðèâîäèìûå ìíîãî÷ëåíû.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà14 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíûÒåîðåìàÊàæäûé ýëåìåíò åâêëèäîâà êîëüöà îäíîçíà÷íî ñ òî÷íîñòüþ äîïåðåñòàíîâîê ðàçëàãàåòñÿ â ïðîèçâåäåíèå ïðîñòûõ ýëåìåíòîâ.Ïðîñòûå (íåðàçëîæèìûå) ýëåìåíòû êîëåöñïåöèàëüíîå íàçâàíèå k[x]èìåþòíåïðèâîäèìûå ìíîãî÷ëåíû.Ñâîéñòâî ¾íåïðèâîäèìîñòè¿ çàâèñèò îò ïîëÿ:ìíîãî÷ëåíx4 + 1 íåïðèâîäèì íàä Q, íî ïðèâîäèìx4 + 1 = (x3 + x2 + x + 1) · (x + 1).Âîïðîñû äëÿ ïîëåé:1êàêèå ìíîãî÷ëåíû íàä íèìè íåïðèâîäèìû?2êàê íàõîäèòü íåïðèâîäèìûå ìíîãî÷ëåíû?íàäF2 :ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä C, R è Q:15 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà15 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä C, R è Q:â ïîëå C òîëüêî ìíîãî÷ëåíû1-éñòåïåíè;ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà15 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä C, R è Q:â ïîëå Câ ïîëå R òîëüêî ìíîãî÷ëåíû1-éñòåïåíè;1ìíîãî÷ëåíû1-éñòåïåíè,2ìíîãî÷ëåíû2-éñòåïåíè ñ îòðèöàòåëüíûìäèñêðèìèíàíòîì;ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà15 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä C, R è Q:â ïîëå Câ ïîëå R òîëüêî ìíîãî÷ëåíû1-éñòåïåíè;1ìíîãî÷ëåíû1-éñòåïåíè,2ìíîãî÷ëåíû2-éñòåïåíè ñ îòðèöàòåëüíûìäèñêðèìèíàíòîì;â ïîëå Q ñóùåñòâóþò íåïðèâîäèìûå ìíîãî÷ëåíûïðîèçâîëüíîé ñòåïåíè.Äàëåå íàñ áóäóò èíòåðåñîâàòü íåïðèâîäèìûåìíîãî÷ëåíû â êîíå÷íûõ ïîëÿõ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F2ÏðèìåðÄàíîF2 = h {0, 1}, +2 , ·2 iÒðåáóåòñÿ: ïîëå.: íàéòè âñå íåïðèâîäèìûå ìíîãî÷ëåíû ñòåïåíåé2, 3, 4íàä íèì.16 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà16 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F2ÏðèìåðÄàíîF2 = h {0, 1}, +2 , ·2 iÒðåáóåòñÿ: ïîëå.: íàéòè âñå íåïðèâîäèìûå ìíîãî÷ëåíû ñòåïåíåé2, 3, 4íàä íèì.Âòîðàÿ ñòåïåíü: x2 + ax + bßñíî, ÷òîíåïðèâîäèìûéÅñëèx2 + ax = x(x + a) ⇒ èùåì2ìíîãî÷ëåí â âèäå x + ax + 1.b = 1,,,a=0a=1òîèíà÷åx2 + 1 = (x + 1)2 ;òî ïîëó÷àåìåäèíñòâåííûé íåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíèx2+x+12íàäF2 :ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà17 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F2Òðåòüÿ ñòåïåíü: x3 + ax2 + bx + 1(ïî÷åìó ñâîáîäíûé ÷ëåí íå ðàâåí íóëþ?)Èñêëþ÷àÿ, êàê ñäåëàíî ðàíåå, äåëèìîñòü íàóñëîâèåa + b 6= 0,ò.å.a = 0, b = 1 ,a = 1, b = 0 .x + 1,ïîëó÷àåìÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà17 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F2Òðåòüÿ ñòåïåíü: x3 + ax2 + bx + 1(ïî÷åìó ñâîáîäíûé ÷ëåí íå ðàâåí íóëþ?)Èñêëþ÷àÿ, êàê ñäåëàíî ðàíåå, äåëèìîñòü íàóñëîâèåa + b 6= 0,íàäïîëó÷àåìò.å.∴x + 1,a = 0, b = 1 ,a = 1, b = 0 .F2 ñóùåñòâóåò äâà íåïðèâîäèìûõ ìíîãî÷ëåíà ñòåïåíèx3 + x2 + 1èx3 + x + 1 .3:ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà18 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F2×åòâ¼ðòàÿ ñòåïåíü:x4 + ax3 + bx2 + cx + 1Èñêëþ÷åíèå äåëèìîñòè íà x + 1 ïðèâîäèò ê óñëîâèþa + b + c = 1, ò.å. èìååòñÿ 4 âàðèàíòà, êîòîðûå äàþò 3a0011b0101c1001ðåøåíèÿ:ìíîãî÷ëåíx4 + x + 1x4 + x2 + 1x4 + x3 + 1x4 + x3 + x2 + x + 1 ïðèâîäèìûéÎòêóäà âçÿëñÿ åù¼ îäèí ïðèâîäèìûé ìíîãî÷ëåí?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà18 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F2×åòâ¼ðòàÿ ñòåïåíü:x4 + ax3 + bx2 + cx + 1Èñêëþ÷åíèå äåëèìîñòè íà x + 1 ïðèâîäèò ê óñëîâèþa + b + c = 1, ò.å.
èìååòñÿ 4 âàðèàíòà, êîòîðûå äàþò 3a0011b0101c1001ðåøåíèÿ:ìíîãî÷ëåíx4 + x + 1x4 + x2 + 1x4 + x3 + 1x4 + x3 + x2 + x + 1 ïðèâîäèìûéÎòêóäà âçÿëñÿ åù¼ îäèí ïðèâîäèìûé ìíîãî÷ëåí?Íàéäåíû ìíîãî÷ëåíû, ó êîòîðûõ íåò ëèíåéíûõ äåëèòåëåé(ñòåïåíè1).Íî ìíîãî÷ëåí4-éñòåïåíè ìîæåò ðàçëàãàòüñÿ âïðîèçâåäåíèå äâóõ íåïðèâîäèìûõ ìíîãî÷ëåíîâx4+x2+1 =(x2+x+1)2 .2-éñòåïåíè:ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà19 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F3ÏîëåF3={0, 1, 2}, +3 , ·3⇒êîëüöî ìíîãî÷ëåíîâF3 [x].ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà19 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F3ÏîëåF3={0, 1, 2}, +3 , ·3⇒êîëüöî ìíîãî÷ëåíîâÌíîãî÷ëåíû ïîðÿäêà 1:x2xx+12x + 1x+22x + 2Êàêèå èç íèõ íåïðèâîäèìû?F3 [x].ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà19 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F3ÏîëåF3={0, 1, 2}, +3 , ·3⇒êîëüöî ìíîãî÷ëåíîâÌíîãî÷ëåíû ïîðÿäêà 1:x2xx+12x + 1x+22x + 2Êàêèå èç íèõ íåïðèâîäèìû? Âñå!F3 [x].ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà19 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÍåïðèâîäèìûå ìíîãî÷ëåíû íàä F3ÏîëåF3={0, 1, 2}, +3 , ·3⇒êîëüöî ìíîãî÷ëåíîâF3 [x].Ìíîãî÷ëåíû ïîðÿäêà 1:x2xx+12x + 1x+22x + 2Êàêèå èç íèõ íåïðèâîäèìû? Âñå!Íåïðèâîäèìûå ìíîãî÷ëåíû ïîðÿäêàêîðíåé2âF3 [x] (îíè íå èìåþò0, 1, 2):x2 + 12x2 + 2x2 + x + 22x2 + x + 1x2 + 2x + 22x2 + 2x + 1ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
