Конечные поля (часть 1) (1127160), страница 5
Текст из файла (страница 5)
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà36 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà ïðèìåíÿþò äëÿ íàõîæäåíèÿ ÍÎÄ(a, b) íàòóðàëüíûõÍàáëþäåíèå(a, b),a > b).: îáùèé äåëèòåëü ïàðû ÷èñåëèì è äëÿ ïàðûÎòñþäà(a − b, b)(ñ÷èòàåì, ÷òîaèb.òî îñòà¼òñÿ:ïàðû ÷èñåëäåëèòåëè;(a, b)è(a − kb, b)èìååò îäèíàêîâûå îáùèåÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà36 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà ïðèìåíÿþò äëÿ íàõîæäåíèÿ ÍÎÄ(a, b) íàòóðàëüíûõÍàáëþäåíèå(a, b),a > b).: îáùèé äåëèòåëü ïàðû ÷èñåëèì è äëÿ ïàðûÎòñþäà(a − b, b)(ñ÷èòàåì, ÷òîaèb.òî îñòà¼òñÿ:ïàðû ÷èñåë(a, b)è(a − kb, b)èìååò îäèíàêîâûå îáùèåäåëèòåëè;âìåñòîa − kbr0b : a = bq + r0 , q ∈ N, 0 6 r0 < b;(äëÿ ¾óñêîðåíèÿ¿) ìîæíî âçÿòü îñòàòîêîò äåëåíèÿ íàöåëîaíàÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà36 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà ïðèìåíÿþò äëÿ íàõîæäåíèÿ ÍÎÄ(a, b) íàòóðàëüíûõÍàáëþäåíèå(a, b),a > b).: îáùèé äåëèòåëü ïàðû ÷èñåëèì è äëÿ ïàðûÎòñþäà(a − b, b)(ñ÷èòàåì, ÷òîaèb.òî îñòà¼òñÿ:ïàðû ÷èñåë(a, b)è(a − kb, b)èìååò îäèíàêîâûå îáùèåäåëèòåëè;âìåñòîa − kbr0b : a = bq + r0 , q ∈ N, 0 6 r0 < b;(äëÿ ¾óñêîðåíèÿ¿) ìîæíî âçÿòü îñòàòîêîò äåëåíèÿ íàöåëîaíàçàòåì, ïåðåñòàâèâ ÷èñëà â ïàðå, ìîæíî ïîâòîðèòüïðîöåäóðó; îíà çàêîí÷èòñÿ, ò.ê. ÷èñëà â ïàðå óìåíüøàþòñÿ,íî îñòàþòñÿ íåîòðèöàòåëüíûìè.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà36 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà ïðèìåíÿþò äëÿ íàõîæäåíèÿ ÍÎÄ(a, b) íàòóðàëüíûõÍàáëþäåíèå(a, b),a > b).: îáùèé äåëèòåëü ïàðû ÷èñåëèì è äëÿ ïàðûÎòñþäà(a − b, b)(ñ÷èòàåì, ÷òîaèb.òî îñòà¼òñÿ:ïàðû ÷èñåë(a, b)è(a − kb, b)èìååò îäèíàêîâûå îáùèåäåëèòåëè;âìåñòîa − kbr0b : a = bq + r0 , q ∈ N, 0 6 r0 < b;(äëÿ ¾óñêîðåíèÿ¿) ìîæíî âçÿòü îñòàòîêîò äåëåíèÿ íàöåëîaíàçàòåì, ïåðåñòàâèâ ÷èñëà â ïàðå, ìîæíî ïîâòîðèòüïðîöåäóðó; îíà çàêîí÷èòñÿ, ò.ê.
÷èñëà â ïàðå óìåíüøàþòñÿ,íî îñòàþòñÿ íåîòðèöàòåëüíûìè. ðåçóëüòàòå: çà êîíå÷íîå ÷èñëî øàãîâ îáðàçóåòñÿ ïàðàè ÿñíî, ÷òî ÍÎÄ(a, b)= rn( ÍÎÄ àíãë. gcd).(rn , 0)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà36 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà ïðèìåíÿþò äëÿ íàõîæäåíèÿ ÍÎÄ(a, b) íàòóðàëüíûõÍàáëþäåíèå(a, b),a > b).: îáùèé äåëèòåëü ïàðû ÷èñåëèì è äëÿ ïàðûÎòñþäà(a − b, b)(ñ÷èòàåì, ÷òîaèb.òî îñòà¼òñÿ:ïàðû ÷èñåë(a, b)è(a − kb, b)èìååò îäèíàêîâûå îáùèåäåëèòåëè;âìåñòîa − kbr0b : a = bq + r0 , q ∈ N, 0 6 r0 < b;(äëÿ ¾óñêîðåíèÿ¿) ìîæíî âçÿòü îñòàòîêîò äåëåíèÿ íàöåëîaíàçàòåì, ïåðåñòàâèâ ÷èñëà â ïàðå, ìîæíî ïîâòîðèòüïðîöåäóðó; îíà çàêîí÷èòñÿ, ò.ê.
÷èñëà â ïàðå óìåíüøàþòñÿ,íî îñòàþòñÿ íåîòðèöàòåëüíûìè. ðåçóëüòàòå: çà êîíå÷íîå ÷èñëî øàãîâ îáðàçóåòñÿ ïàðàè ÿñíî, ÷òî ÍÎÄ(a, b)= rn(rn , 0)( ÍÎÄ àíãë. gcd).Íà÷àëàõ Åâêëèäà,Òîïèêå Àðèñòîòåëÿ).Äàííûé àëãîðèòì äâàæäû îïèñàí âáûë èì îòêðûò (óïîìèíàåòñÿ âíî íåÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà37 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà: îáùàÿ ñõåìà (a > b)ÍÎÄ (a, b)=Øàã(−2): r−2 = a ïîëàãàåì äëÿ óäîáñòâà;Øàã(−1): r−1 = b ïîëàãàåì äëÿ óäîáñòâà;Øàã0: r−2 = r−1 q0 + r0Øàã1: r−1 = r0 q1 + r1 äåëèì r−1 íà r0 , îñòàòîê r1 ;... âñåãäà äåëèì ñ îñòàòêîì áîëüøåå ÷èñëî íàìåíüøåå, îñòàâëÿåì ìåíüøåå (îíî ñòàíîâèòñÿáîëüøèì) è îñòàòîê (îí ñòàíîâèòñÿ ìåíüøèì);Øàãn: rn−2 = rn−1 qn + rnîñòàòîê rn ;Øàã äåëèìn + 1: rn−1 = rn qn+1 + 0Âñåãäàr−2 äåëèìíàrn−2r−1 ,íà äåëåíèå íàöåëîr−2 > r−1 > r0 > r1 > .
. . > rn > 1.îñòàòîêr0 ;rn−1 ,⇒îñòàíîâ= rn ..ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÂû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà: ïðèìåðÍÎÄ (252, 105)= 2138 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà38 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà: ïðèìåðÍÎÄ (252, 105)= 21Øàã(−2): r−2 = 252;Øàã(−1): r−1 = 105⇒ (252, 105);Øàã0: 252 = 105 · 2 + 42⇒ (105, 42);Øàã1: 105 = 42 · 2 + 21⇒ (42, 21);Øàã2: 42 = 21 · 2 + 0⇒ (21, 0).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà38 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà: ïðèìåðÍÎÄ (252, 105)= 21Øàã(−2): r−2 = 252;Øàã(−1): r−1 = 105⇒ (252, 105);Øàã0: 252 = 105 · 2 + 42⇒ (105, 42);Øàã1: 105 = 42 · 2 + 21⇒ (42, 21);Øàã2: 42 = 21 · 2 + 0⇒ (21, 0).ÍÎÄ (a, b, c)Èíòåðåñíî: åñëè=ÍÎÄ (a, (ÍÎÄ (b, c))a = Fn+1 , b = Fn ñîîòâåòñòâóþùèå ÷èñëàÔèááîíà÷è, òî îñòàòêè â àëãîðèòìå Åâêëèäà ïîñëåäîâàòåëüíîäàäóò çíà÷åíèÿFn−1 , .
. ., F2 = 1.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà39 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÑîîòíîøåíèå Áåçó (îòêðûòî çà 106 ëåò äî ðîæäåíèÿ Ý.Áåçó)Óòâåðæäåíèå (ñîîòíîøåíèå Áåçó)Äëÿ ëþáûõ íàòóðàëüíûõ a, b è d = ÍÎÄ (a, b) íàéäóòñÿöåëûå êîýôôèöèåíòû Áåçó x, y òàêèå, ÷òî d = ax + by .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà39 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÑîîòíîøåíèå Áåçó (îòêðûòî çà 106 ëåò äî ðîæäåíèÿ Ý.Áåçó)Óòâåðæäåíèå (ñîîòíîøåíèå Áåçó)Äëÿ ëþáûõ íàòóðàëüíûõ a, b è d = ÍÎÄ (a, b) íàéäóòñÿöåëûå êîýôôèöèåíòû Áåçó x, y òàêèå, ÷òî d = ax + by .ÄîêàçàòåëüñòâîÐàññìàòðèâàåì àëãîðèòì Åâêëèäà ñ êîíöà ê íà÷àëó:d = rn = rn−2 − rn−1 qn , çàòåì, ïîäñòàâëÿÿ ñþäà çíà÷åíèårn−1 = rn−3 − rn−2 qn−1 , ïîëó÷àåìd = −qn rn−3 + (1 + qn qn−1 )rn−2 = αrn−3 + βrn−2äëÿ íåêîòîðûõ α, β ∈ Z è ò.ä.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà39 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÑîîòíîøåíèå Áåçó (îòêðûòî çà 106 ëåò äî ðîæäåíèÿ Ý.Áåçó)Óòâåðæäåíèå (ñîîòíîøåíèå Áåçó)Äëÿ ëþáûõ íàòóðàëüíûõ a, b è d = ÍÎÄ (a, b) íàéäóòñÿöåëûå êîýôôèöèåíòû Áåçó x, y òàêèå, ÷òî d = ax + by .ÄîêàçàòåëüñòâîÐàññìàòðèâàåì àëãîðèòì Åâêëèäà ñ êîíöà ê íà÷àëó:d = rn = rn−2 − rn−1 qn , çàòåì, ïîäñòàâëÿÿ ñþäà çíà÷åíèårn−1 = rn−3 − rn−2 qn−1 , ïîëó÷àåìd = −qn rn−3 + (1 + qn qn−1 )rn−2 = αrn−3 + βrn−2äëÿ íåêîòîðûõ α, β ∈ Z è ò.ä.Çàìå÷àíèåÊîýôôèöèåíòû Áåçó îïðåäåëåíû íåîäíîçíà÷íî:ÍÎÄ (12, 30)= 6 = 3 · 12 + (−1) · 30 = (−2) · 12 + 1 · 30.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà40 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÐàñøèðåííûé àëãîðèòì Åâêëèäà ïîâòîðÿåò ñõåìó (ïðîñòîãî) àëãîðèòìà Åâêëèäà, â êîòîðîìíà êàæäîì øàãå:1äîïîëíèòåëüíî âû÷èñëÿþòñÿxi = xi−2 − qi xi−1 ,xiyiïî ôîðìóëàìyi = yi−2 − qi yi−1 ,x−2 = y−1 = 1 ,2èi = 0, 1, ...;x−1 = y−2 = 0 ;ñïðàâåäëèâî ñîîòíîøåíèåri = ri−2 − qi ri−1 = (axi−2 + byi−2 ) − qi (axi−1 + byi−1 ) == a(xi−2 − qi xi−1 ) + b(yi−2 − qi yi−1 ) = axi + byi .Ðàñøèðåííûé àëãîðèòì Åâêëèäà ïî äâóì íàòóðàëüíûì ÷èñëàìaèbíàõîäèò èõ íàòóðàëüíûéêîýôôèöèåíòà Áåçó (òàêèõ, ÷òîÍÎÄ dè äâà öåëûõ|x| < |b/d|, |y| < |a/d|).x, yÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà41 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÐàñøèðåííûé àëãîðèòì Åâêëèäà: ïðèìåðÇàäà÷àdxy. Íàéòè íàòóðàëüíîåd =Ðåøåíèå. Èìååìè öåëûåÍÎÄ (252, 105)èòàêèå, ÷òî= 252x + 105y .xi = xi−2 − qi xi−1 , yi = yi−2 − qi yi−1 .Ñâåä¼ì âñå âû÷èñëåíèÿ â òàáëèöó:i−2−1012øàãÎòâåò:ri−2ri−1qi252105421054221222d = 21, x = −2, y = 5,ò.å.ri25210542210xi101−2yi01−2521 = 252 · (−2) + 105 · 5.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà42 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÇàäà÷à ïîëåZ/(101)ðåøèòü óðàâíåíèå4x = 1.(∗)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà42 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÇàäà÷à ïîëåZ/(101)ðåøèòü óðàâíåíèå4x = 1.(∗)Ðåøåíèå14x = 1 + k · 101 = 102, 203, 304, . . . ;Ýòî ðåøåíèå ïåðåáîðîì.x = 304/4 = 76.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà42 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÇàäà÷à ïîëåZ/(101)ðåøèòü óðàâíåíèå4x = 1.(∗)Ðåøåíèå14x = 1 + k · 101 = 102, 203, 304, . . .
;x = 304/4 = 76.Ýòî ðåøåíèå ïåðåáîðîì.2Ïîñêîëüêó101y ≡101 0,âìåñòî(∗)ìîæíî ðàñøèðåííûìàëãîðèòìîì Åâêëèäà ðåøàòü óðàâíåíèå4x + 101y = 1 .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà42 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÇàäà÷à ïîëåZ/(101)ðåøèòü óðàâíåíèå4x = 1.(∗)Ðåøåíèå14x = 1 + k · 101 = 102, 203, 304, . . . ;x = 304/4 = 76.Ýòî ðåøåíèå ïåðåáîðîì.2Ïîñêîëüêó101y ≡101 0,âìåñòî(∗)ìîæíî ðàñøèðåííûìàëãîðèòìîì Åâêëèäà ðåøàòü óðàâíåíèå4x + 101y = 1 . ðåçóëüòàòå ðàáîòû àëãîðèòìà:4 · 76 + 101 · (−3) = 1.Àíàëîãè÷íî ðåøàþòñÿ óðàâíåíèÿax = c(ïåðåä ðåøåíèåìa, bècèax + by = cíàäî ïîäåëèòü íà èõ îáùèé ÍÎÄ).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà43 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÍàõîæäåíèå îáðàòíûõ ýëåìåíòîâ â ðàñøèðåíèÿõ ïîëåé FpÀëãîðèòì Åâêëèäà è åãî ðàñøèðåííàÿ âåðñèÿ îñòàþòñÿñïðàâåäëèâûìè â ëþáîì åâêëèäîâîì êîëüöå, ñëåäîâàòåëüíî,è â ëþáîì ïîëå Ãàëóà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà43 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÍàõîæäåíèå îáðàòíûõ ýëåìåíòîâ â ðàñøèðåíèÿõ ïîëåé FpÀëãîðèòì Åâêëèäà è åãî ðàñøèðåííàÿ âåðñèÿ îñòàþòñÿñïðàâåäëèâûìè â ëþáîì åâêëèäîâîì êîëüöå, ñëåäîâàòåëüíî,è â ëþáîì ïîëå Ãàëóà.Ïîýòîìób(x): îáðàòíûé ýëåìåíòâ ïîëåF = Fp [x]/(a(x))b(x) · y(x) = 1⇔y(x)äëÿ íåêîòîðîãî ìíîãî÷ëåíàîïðåäåëÿåòñÿ ñîîòíîøåíèåìa(x) · χ(x) + b(x) · y(x) = 1 ,êîòîðîå ìîæåò áûòü ðåøåíî ðàñøèðåííûì àëãîðèòìîìÅâêëèäà äëÿ ïàðû ìíîãî÷ëåíîâ(a(x), b(x))â ïîëåÐåøåíèå äàííûõ óðàâíåíèé ñóùåñòâóåò âñåãäà: ò.ê.íåïðèâîäèìûé ìíîãî÷ëåí èÍÎÄ (a(x),b(x)) = 1.deg b(x) < deg a(x),òîF.a(x)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà44 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÏðèìåð: íàéòè (x2 + x + 3)−1 â ïîëå F7[x]/ x4 + x3 + x2 + 3ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà44 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÏðèìåð: íàéòè (x2 + x + 3)−1 â ïîëå F7[x]/ x4 + x3 + x2 + 3Ïðèìåíÿÿ ðàñøèðåííûé àëãîðèòì Åâêëèäà, ðåøèì óðàâíåíèå(x4 + x3 + x2 + 3)χ(x) + (x2 + x + 3)y(x) = 1(∗)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà44 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÏðèìåð: íàéòè (x2 + x + 3)−1 â ïîëå F7[x]/ x4 + x3 + x2 + 3Ïðèìåíÿÿ ðàñøèðåííûé àëãîðèòì Åâêëèäà, ðåøèì óðàâíåíèå(x4 + x3 + x2 + 3)χ(x) + (x2 + x + 3)y(x) = 1Øàã 0:Øàã 1:Øàã 2:(∗)r−2 (x) = x4 + x3 + x2 + 3,r−1 (x) = x2 + x + 3,y−2 (x) = 0,y−1 (x) = 1 çàäàíèå íà÷àëüíûõ çíà÷åíèé.r−2 (x) = r−1 (x)q0 (x) + r0 (x),q0 (x) = x2 + 5,r0 (x) = 2x + 2,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = −x2 − 5.r−1 (x) = r0 (x)q1 (x) + r1 (x),q1 (x) = 4x,r1 (x) = 3, deg r1 (x) = 0y1 (x) = y−1 (x) − y0 (x)q1 (x) = 1 + 4x(x2 + 5) == 4x3 + 6x + 1.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà45 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÏðèìåð...F47 :(x4 + x3 + x2 + 3)χ(x) + b(x)(x2 + x + 3) = 1 (∗)Àëãîðèòì çàêàí÷èâàåò ñâîþ ðàáîòó íà øàãådeg r1 (x) = deg 1 = 02,ò.ê.r1 (x) = 3(∗) ).( 1 ìíîãî÷ëåí â ïðàâîé ÷àñòèèÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà45 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÏðèìåð...F47 :(x4 + x3 + x2 + 3)χ(x) + b(x)(x2 + x + 3) = 1 (∗)Àëãîðèòì çàêàí÷èâàåò ñâîþ ðàáîòó íà øàãådeg r1 (x) = deg 1 = 0Çàìå÷àíèåâû÷èñëÿòüò.ê.r1 (x) = 3(∗) ).: ïðè èòåðàöèÿõ àëãîðèòìà íåò íåîáõîäèìîñòèχi (x)x4 + x3 + x2 + 3, ò.ê.2êîýôôèöèåíò ïðè x + x + 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
