Конечные поля (часть 1) (1127160), страница 7
Текст из файла (страница 7)
. , xn−1 ; êàæäûén ýëåìåíòáàçèñå êàæäûé íåíóëåâîé ýëåìåíòFêàê íåêîòîðàÿ ñòåïåíü ãåíåðàòîðàêàê âåêòîð âçàïèñûâàåòñÿαãðóïïûF ∗.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà54 / 95Âåêòîðíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÏðåäñòàâëåíèå ýëåìåíòîâ êîíå÷íîãî ïîëÿ: ðåçþìåÍàèáîëåå óïîòðåáèìû äâà ïðåäñòàâëåíèÿ ýëåìåíòîâ êîíå÷íîãîF = Fp [x]/(a(x)) ∼=deg a(x) = n):ïîëÿâåêòîðíîåñòåïåííîåÇàìå÷àíèåFnp(ïîëèíîìa(x)íåïðèâîäèì,F çàïèñûâàåòñÿo1, x1 , x2 , . . .
, xn−1 ; êàæäûén ýëåìåíòáàçèñå êàæäûé íåíóëåâîé ýëåìåíòFêàê íåêîòîðàÿ ñòåïåíü ãåíåðàòîðàêàê âåêòîð âçàïèñûâàåòñÿαãðóïïûF ∗.. Ïåðåõîä îò ñòåïåííîãî ïðåäñòàâëåíèÿ êâåêòîðíîìó äîñòàòî÷íî ïðîñò, à îáðàòíûé ïåðåõîä î÷åíüäèñêðåòíîãî ëîãàðèôìàαz = b).ñëîæåí (ñâÿçàí ñ âû÷èñëåíèåìíàòóðàëüíîãîzâ ðàâåíñòâåÍà ñëîæíîñòè ýòîé çàäà÷è (èçâåñòíû íå áîëåå, ÷åìñóáýêñïîíåíöèàëüíûå àëãîðèòìû å¼ ðåøåíèÿ) áàçèðóþòñÿìåòîäû êðèïòîãðàôèè ñ îòðûòûì êëþ÷îì.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÐàçäåëû1234567Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÂåêòîðíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ GF (pn)Öèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è ñ ðåøåíèÿìè55 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà56 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌèíèìàëüíûé ìíîãî÷ëåíÐàññìîòðèì ýëåìåíòβêîíå÷íîãî ïîëÿ è áóäåì èíòåðåñîâàòüñÿìíîãî÷ëåíàìè, äëÿ êîòîðûõ îí ÿâëÿåòñÿ êîðíåì.ÎïðåäåëåíèåÌèíèìàëüíûì ìíîãî÷ëåíîì (ì.ì.)β ∈ GF (pn )íàçûâàåòñÿ ïðèâåä¼ííûé ìíîãî÷ëåí mβ (x) ∈ Fp [x]íàèìåíüøåé ñòåïåíè, äëÿ êîòîðîãî β ÿâëÿåòñÿ êîðíåì.ýëåìåíòàÄðóãèìè ñëîâàìè, äîëæíû âûïîëíÿòüñÿ òðè óñëîâèÿ:1mβ (β) = 0;2∀ f (x) ∈ Fp [x] : deg f (x) < deg mβ (x) ⇒ f (β) 6= 0;3êîýôôèöèåíò ïðè ñòàðøåé ñòåïåíè âmβ (x)ðàâåí1.Ïî÷òè î÷åâèäíî, ÷òî ì.ì.
íåïðèâîäèìûé (äîêàæåì ïîñëå).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà57 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌèíèìàëüíûé ìíîãî÷ëåí èç íåïðèâîäèìîãîÐàññìîòðèì ïîëåF =Fp [x]/(a(x)), ïîðîæäàåìîåa(x) = a0 + a1 x + . . . + an xn−1óáåäèìñÿ, ÷òî ìíîãî÷ëåí an a(x) ìèíèìàëüíûé äëÿýëåìåíòà x = ( 0, 1, 0, . . . , 0 ) ∈ F .íåïðèâîäèìûì ìíîãî÷ëåíîìèÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà57 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌèíèìàëüíûé ìíîãî÷ëåí èç íåïðèâîäèìîãîÐàññìîòðèì ïîëåF =Fp [x]/(a(x)), ïîðîæäàåìîåa(x) = a0 + a1 x + . .
. + an xn−1óáåäèìñÿ, ÷òî ìíîãî÷ëåí an a(x) ìèíèìàëüíûé äëÿýëåìåíòà x = ( 0, 1, 0, . . . , 0 ) ∈ F .íåïðèâîäèìûì ìíîãî÷ëåíîìèßñíî, ÷òîx2 = x2 = (0, 0, 1, 0, . . . , 0),Äàëåå, ñ îäíîé ñòîðîíûx..., êîðåíüxn−1 = (0, . . . , 0, 1)a(x):a0 + a1 x + . . . + an (x)n = a0 + a1 x + . . . + an xn = 0,à çíà÷èò èa−1n a(x).∃ b(x) = b0 + b1 x + . . . + bn−1 (x)n−1 = 0, òîb0 + b1 x + . . . + bn−1 xn−1 = 0, ò.å.n èìååì ëèíåéíóþoçàâèñèìîñòü ìåæäó ýëåìåíòàìè1, x, . . . , xn−1 áàçèñàïîëÿ F êàê âåêòîðíîãî ïðîñòðàíñòâà íàä Fp , îòêóäàb0 = b1 = .
. . = bn−1 = 0.Ñ äðóãîé åñëèÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà57 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌèíèìàëüíûé ìíîãî÷ëåí èç íåïðèâîäèìîãîÐàññìîòðèì ïîëåF =Fp [x]/(a(x)), ïîðîæäàåìîåa(x) = a0 + a1 x + . . . + an xn−1óáåäèìñÿ, ÷òî ìíîãî÷ëåí an a(x) ìèíèìàëüíûé äëÿýëåìåíòà x = ( 0, 1, 0, . . . , 0 ) ∈ F .íåïðèâîäèìûì ìíîãî÷ëåíîìèßñíî, ÷òîx2 = x2 = (0, 0, 1, 0, . . .
, 0),Äàëåå, ñ îäíîé ñòîðîíûx..., êîðåíüxn−1 = (0, . . . , 0, 1)a(x):a0 + a1 x + . . . + an (x)n = a0 + a1 x + . . . + an xn = 0,à çíà÷èò èa−1n a(x).∃ b(x) = b0 + b1 x + . . . + bn−1 (x)n−1 = 0, òîb0 + b1 x + . . . + bn−1 xn−1 = 0, ò.å.n èìååì ëèíåéíóþoçàâèñèìîñòü ìåæäó ýëåìåíòàìè1, x, . . . , xn−1 áàçèñàïîëÿ F êàê âåêòîðíîãî ïðîñòðàíñòâà íàä Fp , îòêóäàb0 = b1 = . . . = bn−1 = 0.Ñ äðóãîé åñëèÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÊñòàòè, ÷òî òàêîå x ?58 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà58 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÊñòàòè, ÷òî òàêîå x ?= Fp [x]/a(x), ãäåa(x) = a0 + a1 x + . . . + an xn íåïðèâîäèìûéÐàññìàòðèâàåì ïîëåFnpìíîãî÷ëåí,ò.å.
â ýòîì ïîëåa(x) = 0 ⇔ xn = an −1 −a0 − a1 x − . . . − an−1 xn−1.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà58 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÊñòàòè, ÷òî òàêîå x ?= Fp [x]/a(x), ãäåa(x) = a0 + a1 x + . . . + an xn íåïðèâîäèìûéÐàññìàòðèâàåì ïîëåFnpìíîãî÷ëåí,ò.å. â ýòîì ïîëåa(x) = 0 ⇔ xn = an −1 −a0 − a1 x − . . . − an−1 xn−11.x = { f (x) ∈.Fp [x] | f (x) = q(x)a(x)+x, q(x) ∈ Fp [x] }.Fnp == f (x) = b0 + b1 x + . . . + bn−1 xn−1 | b0 , b1 , . . . , bn−1 ∈ Fp == { (b0 , b1 , .
. . , bn−1 ) | b0 , b1 , . . . , bn−1 ∈ Fp }2.x = { (0, 1, 0, . . . , 0) | 1 ∈ Fp }. äàëüíåéøåì, êàê ïðèíÿòî, âìåñòîx÷àñòî ïèøåì ïðîñòîx.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìßâëÿþòñÿ ëè ìèíèìàëüíûå ìíîãî÷ëåíû ïðèìèòèâíûìè?59 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà59 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìßâëÿþòñÿ ëè ìèíèìàëüíûå ìíîãî÷ëåíû ïðèìèòèâíûìè?Ïðèìåðûèç ïðåäûäóùåãî.a(x) = x3 + x + 1 íåïðèâîäèì â F2 [x],ñëåäîâàòåëüíî F = F2 [x]/(a(x)) ïîëå è ïî äîêàçàííîìóðàíåå a(x) ìèíèìàëüíûé ìíîãî÷ëåí äëÿ x.¶Ìíîãî÷ëåíÏðèìèòèâåí ëèa(x)?F = GF (23 ) a(x) 6 | (xt − 1) ïðèt = 3, 4, 5, 6 (à äåëèìîñòü x7 − 1 íà a(x) âñåãäà áóäåò7342ìåñòî: x + 1 = (x + x + 1)(x + x + x + 1)).Ïðîâåðÿåì, ÷òî âÝòî îçíà÷àåò, ÷òîxa(x)èìåòü ïðèìèòèâíûé ìíîãî÷ëåí è ïðèìèòèâíûé ýëåìåíò ïîëÿF(ãåíåðàòîðF ∗ , deg x = 7).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà60 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìßâëÿþòñÿ ëè ìèíèìàëüíûå ìíîãî÷ëåíû ïðèìèòèâíûìè...·Ìíîãî÷ëåíñëåäîâàòåëüíîðàíååa(x)a(x) = x4 + x3 + x2 + x + 1F = F2 [x]/(a(x)) ïîëå è ìèíèìàëüíûé ìíîãî÷ëåí äëÿÏðèìèòèâåí ëèÈìååì âíåïðèâîäèì âF2 [x],ïî äîêàçàííîìóx.a(x)?F = GF (24 ):a(x) | (x5 − 1) : x5 + 1 = (x4 + x3 + x2 + x + 1)(x + 1).Ýòî îçíà÷àåò, ÷òîx íå ãåíåðàòîða(x) íå åñòü ïðèìèòèâíûéF ∗ , ò.ê. deg x = 5 6= 15.ìíîãî÷ëåí èÄðóãîå îïðåäåëåíèå: ìèíèìàëüíûé ìíîãî÷ëåí ïðèìèòèâíîãîýëåìåíòà ïîëÿ íàçûâàåòñÿïðèìèòèâíûì ìíîãî÷ëåíîì.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà61 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíîãî ìíîãî÷ëåíàmβ (x) ∈ Fnp: ðåçþìåÄàííûå ñâîéñòâà áóäóò äîêàçàíû äàëåå.1Ìíîãî÷ëåí23Åñëè f (x) òàêîémβ (x) | f (x).nmβ (x) | xp − x .4deg mβ (x) 6 n.5Ìíîãî÷ëåímβ (x)mβ (x)íåïðèâîäèì.ìíîãî÷ëåí, ÷òîf (β) = β , ìèíèìàëüíûé äëÿβèòîβp.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÌíîãî÷ëåíû:62 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâÓòâåðæäåíèåÌèíèìàëüíûå ìíîãî÷ëåíû íåïðèâîäèìû.63 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâÓòâåðæäåíèåÌèíèìàëüíûå ìíîãî÷ëåíû íåïðèâîäèìû.ÄîêàçàòåëüñòâîÏóñòü mβ (x) ì.ì. äëÿ β è mβ (x) = m1 (x)m2 (x).Òîãäàm1 (β) = 0mβ (β) = 0 ⇒,m2 (β) = 0íî deg m1 < deg m è deg m2 < deg m ⇒ β íå ìîæåò áûòüêîðíåì íè m1 (x), íè m2 (x).63 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâ...ÓòâåðæäåíèåÏóñòü â íåêîòîðîì ïîëå Ãàëóà mβ (x) ì.ì.
äëÿ ýëåìåíòà β , àf (x) ìíîãî÷ëåí òàêîé, ÷òî f (β) = 0.Òîãäà f (x) äåëèòñÿ íà mβ (x).64 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâ...ÓòâåðæäåíèåÏóñòü â íåêîòîðîì ïîëå Ãàëóà mβ (x) ì.ì. äëÿ ýëåìåíòà β , àf (x) ìíîãî÷ëåí òàêîé, ÷òî f (β) = 0.Òîãäà f (x) äåëèòñÿ íà mβ (x).ÄîêàçàòåëüñòâîÐàçäåëèì f (x) íà mβ (x) ñ îñòàòêîì:f (x) = u(x)mβ (x) + v(x) ,deg v < deg m .Ïîäñòàâëÿÿ â ýòî ðàâåíñòâî β âìåñòî x, ïîëó÷àåì0 = f (β) = u(β) mβ (β) +v(β) = v(β) ,| {z }=0ò.å. β êîðåíü v(x), ÷òî ïðîòèâîðå÷èò ìèíèìàëüíîñòè mβ (x).64 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâ...ÑëåäñòâèåÄëÿ êàæäîãî ýëåìåíòà ïîëÿ ñóùåñòâóåò íå áîëåå îäíîãî ì.ì.65 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâ...ÑëåäñòâèåÄëÿ êàæäîãî ýëåìåíòà ïîëÿ ñóùåñòâóåò íå áîëåå îäíîãî ì.ì.ÄîêàçàòåëüñòâîÏóñòü ìèíèìàëüíûõ ìíîãî÷ëåíîâ äâà.Îíè âçàèìíî äåëÿò äðóã äðóãà, à çíà÷èò, ðàçëè÷àþòñÿ íàîáðàòèìûé ìíîæèòåëü-êîíñòàíòó.Ïîñêîëüêó ìèíèìàëüíûé ìíîãî÷ëåí íîðìèðîâàí, ýòà êîíñòàíòàðàâíà 1, ò.å. äàííûå ìíîãî÷ëåíû ñîâïàäàþò.65 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâ...ÓòâåðæäåíèåÄëÿ êàæäîãî ýëåìåíòà β ïîëÿ Fnp ñóùåñòâóåò (åäèíñòâåííîñòüäîêàçàíà ðàíåå) ì.ì. è åãî ñòåïåíü íå ïðåâîñõîäèò n.66 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà66 / 95Êîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâ...ÓòâåðæäåíèåÄëÿ êàæäîãî ýëåìåíòà β ïîëÿ Fnp ñóùåñòâóåò (åäèíñòâåííîñòüäîêàçàíà ðàíåå) ì.ì.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
