Конечные поля (часть 1) (1127160), страница 4
Текст из файла (страница 4)
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà26 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿ Fnp?f (x)12 ïðèìèòèâíûé ýëåìåíò (ãåíåðàòîð) ãðóïïûf (x)pn −1= 1èf (x)6= 1äëÿ0 < i < p n − 1,g(x) ∈ Fn∗p íàéä¼òñÿ ñòåïåíü iig(x) = f (x) , i ∈ { 0, 1, . . . , pn − 1 }.äëÿ ëþáîãî ìíîãî÷ëåíàòàêàÿ, ÷òîiFn∗p , åñëèÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà26 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿ Fnp?f (x)12 ïðèìèòèâíûé ýëåìåíò (ãåíåðàòîð) ãðóïïûf (x)pn −1= 1èf (x)i6= 1äëÿFn∗p , åñëè0 < i < p n − 1,g(x) ∈ Fn∗p íàéä¼òñÿ ñòåïåíü iig(x) = f (x) , i ∈ { 0, 1, . . . , pn − 1 }.äëÿ ëþáîãî ìíîãî÷ëåíàòàêàÿ, ÷òîÍà îñíîâå èçâåñòíîãî: åñëèGF (q),α ïðèìèòèâíûé ýëåìåíò ïîëÿòî ëþáîé äðóãîé ïðèìèòèâíûé ýëåìåíò ìîæåò áûòüïîëó÷åí êàê ñòåïåíüq − 1 ⇒ êîëè÷åñòâîϕ(pn − 1).αk ,ãäåk öåëîå âçàèìíî ïðîñòîå ñïðèìèòèâíûõ ýëåìåíòîâ ïîëÿFnpðàâíîÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà26 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÊàê íàéòè ïðèìèòèâíûå ýëåìåíòû ïîëÿ Fnp?f (x)12 ïðèìèòèâíûé ýëåìåíò (ãåíåðàòîð) ãðóïïûf (x)pn −1= 1èf (x)i6= 1äëÿFn∗p , åñëè0 < i < p n − 1,g(x) ∈ Fn∗p íàéä¼òñÿ ñòåïåíü iig(x) = f (x) , i ∈ { 0, 1, . . .
, pn − 1 }.äëÿ ëþáîãî ìíîãî÷ëåíàòàêàÿ, ÷òîαÍà îñíîâå èçâåñòíîãî: åñëèGF (q), ïðèìèòèâíûé ýëåìåíò ïîëÿòî ëþáîé äðóãîé ïðèìèòèâíûé ýëåìåíò ìîæåò áûòüïîëó÷åí êàê ñòåïåíüq − 1 ⇒ êîëè÷åñòâîϕ(pn − 1).Íàïðèìåð, âαk ,ãäåk öåëîå âçàèìíî ïðîñòîå ñïðèìèòèâíûõ ýëåìåíòîâ ïîëÿ9-ýëåìåíòíîìïîëåF23èìååòñÿFnpðàâíîϕ(8) = 41, 3, 5, 7ïðèìèòèâíûõ ýëåìåíòà, îáðàçîâàííûõ ñòåïåíÿìè(÷èñëà, âçàèìíî ïðîñòûå ñ8)óæå íàéäåííîãî ãåíåðàòîðà:x + 1, (x + 1)3 = 2x + 1, (x + 1)5 = 2x + 2, (x + 1)7 = x + 2.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàß ÷òî-òî íå ïîíèìàþ: íåïðèâîäèìûå ìíîãî÷ëåíû ýòîïðèìèòèâíûå ýëåìåíòû?27 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàß ÷òî-òî íå ïîíèìàþ: íåïðèâîäèìûå ìíîãî÷ëåíû ýòîïðèìèòèâíûå ýëåìåíòû?Âåäü áûëî: äëÿ ïîèñêà è òåõ, è äðóãèõ íåò ýôôåêòèâíûõàëãîðèòìîâ...27 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàß ÷òî-òî íå ïîíèìàþ: íåïðèâîäèìûå ìíîãî÷ëåíû ýòîïðèìèòèâíûå ýëåìåíòû?Âåäü áûëî: äëÿ ïîèñêà è òåõ, è äðóãèõ íåò ýôôåêòèâíûõàëãîðèòìîâ...Íåïðèâîäèìûå ìíîãî÷ëåíû èùóò â êîëüöå ìíîãî÷ëåíîâFp [x]íàä ïðîñòûì ïîëåìFp íàïðèìåð, ÷òîáûïîñòðîèòü åãî ðàñøèðåíèå.27 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàß ÷òî-òî íå ïîíèìàþ: íåïðèâîäèìûå ìíîãî÷ëåíû ýòîïðèìèòèâíûå ýëåìåíòû?Âåäü áûëî: äëÿ ïîèñêà è òåõ, è äðóãèõ íåò ýôôåêòèâíûõàëãîðèòìîâ...Íåïðèâîäèìûå ìíîãî÷ëåíû èùóò â êîëüöå ìíîãî÷ëåíîâFp [x]íàä ïðîñòûì ïîëåìFp íàïðèìåð, ÷òîáûïîñòðîèòü åãî ðàñøèðåíèå.Ïðèìèòèâíûå ýëåìåíòû èùóò â ìóëüòèïëèêàòèâíîé ãðóïïåïîëÿFnp íàïðèìåð, ÷òîáû èìåòü óäîáíîå ïðåäñòàâëåíèåíåíóëåâûõ ýëåìåíòîâ ïîëÿ ÷åðåç åãî ñòåïåíè.27 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà27 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàß ÷òî-òî íå ïîíèìàþ: íåïðèâîäèìûå ìíîãî÷ëåíû ýòîïðèìèòèâíûå ýëåìåíòû?Âåäü áûëî: äëÿ ïîèñêà è òåõ, è äðóãèõ íåò ýôôåêòèâíûõàëãîðèòìîâ...Íåïðèâîäèìûå ìíîãî÷ëåíû èùóò â êîëüöå ìíîãî÷ëåíîâFp [x]íàä ïðîñòûì ïîëåìFp íàïðèìåð, ÷òîáûïîñòðîèòü åãî ðàñøèðåíèå.Ïðèìèòèâíûå ýëåìåíòû èùóò â ìóëüòèïëèêàòèâíîé ãðóïïåïîëÿFnp íàïðèìåð, ÷òîáû èìåòü óäîáíîå ïðåäñòàâëåíèåíåíóëåâûõ ýëåìåíòîâ ïîëÿ ÷åðåç åãî ñòåïåíè.Çàìå÷àíèå.  ïîëåGF (pn )ïîíÿòèå ¾íåïðèâîäèìûéìíîãî÷ëåí¿ íå èìååò ñìûñëà: òàì ëþáîé ìíîãî÷ëåí äåëèòñÿ íàëþáîé íåíóëåâîé.Íàïðèìåð, âF3 [x]/x2 + 1:x+1= x.2x + 1ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè ïðèâîäèìûé ìíîãî÷ëåí áûòü ïðèìèòèâíûìýëåìåíòîì?28 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà28 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè ïðèâîäèìûé ìíîãî÷ëåí áûòü ïðèìèòèâíûìýëåìåíòîì?F21Âîçüì¼ì ïîëå2Âîçüì¼ì íåïðèâîäèìûé íàä3Ïîñòðîèì ïîëå= { 0, 1 }.F =F2 [x]/ñîäåðæèò âñå ïîëèíîìû èç4ìíîãî÷ëåíx3 + x + 1 .x3 + x + 1 ∼= F32 ;F2 [x] ñòåïåíè 6 2.îíîP (x) = x2 + x = x(x + 1) ïðèâîäèì âêîëüöå, â ò.÷. â F2 [x], è îí ïðèíàäëåæèò F .Ìíîãî÷ëåíëþáîì5F2ßâëÿåòñÿ ëèP (x) ïðèìèòèâíûì ýëåìåíòîì ïîëÿF?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà28 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè ïðèâîäèìûé ìíîãî÷ëåí áûòü ïðèìèòèâíûìýëåìåíòîì?F21Âîçüì¼ì ïîëå2Âîçüì¼ì íåïðèâîäèìûé íàä3Ïîñòðîèì ïîëå= { 0, 1 }.F =F2 [x]/ñîäåðæèò âñå ïîëèíîìû èç4x3 + x + 1 .x3 + x + 1 ∼= F32 ;F2 [x] ñòåïåíè 6 2.îíîP (x) = x2 + x = x(x + 1) ïðèâîäèì âêîëüöå, â ò.÷.
â F2 [x], è îí ïðèíàäëåæèò F .ßâëÿåòñÿ ëèP (x) ïðèìèòèâíûì ýëåìåíòîì ïîëÿÌóëüòèïëèêàòèâíàÿ ãðóïïà ïîëÿýëåìåíòîâ, ýòî ïðîñòîå ÷èñëîâñåìíîãî÷ëåíÌíîãî÷ëåíëþáîì5F2ϕ(7) = 6⇒Fñîäåðæèò23 − 1 = 7â ìóëüòèïëèêàòèâíàÿ ãðóïïåíååäèíè÷íûõ ýëåìåòîâ ãåíåðàòîðûîòâåò íà îáà âîïðîñà ÄÀ!F?⇒ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà29 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÌîæåò ëè ïðèâîäèìûé ìíîãî÷ëåí áûòü ïðèìèòèâíûìýëåìåíòîì?...α = x2 + x = x(x + 1)3ýëåìåíò ïîëÿ F = F2 [x]/ x + x + 1 .3 F: x = x + 1 èÓäîñòîâåðèìñÿ, ÷òî ïðèìèòèâíûéα = x2 + x,α2 = x4 + x2 = 6 x2 + x+ 6 x2 = x,α3 = α · α2 = x3 + x2 = x2 + x + 1,α4 = (α2 )2 = x2 ,α5 = α2 α3 = x3 + x2 + x = 6 x + 1 + x2 + 6 x = x2 + 1,α6 = x4 + x2 + 1 = x2 + x + x2 + 1 = x + 1,α7 = x2 (x2 + x + 1) = x4 + x3 + x2 = 6 x2 + 6 x+ 6 x + 1+ 6 x2 = 1.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂñåãäà ëè íåïðèâîäèìûé ìíîãî÷ëåí åñòü ïðèìèòèâíûéýëåìåíò?30 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà30 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂñåãäà ëè íåïðèâîäèìûé ìíîãî÷ëåí åñòü ïðèìèòèâíûéýëåìåíò?F51Âîçüì¼ì ïîëå2Âîçüì¼ì íåïðèâîäèìûé íàä3Ïîñòðîèì ïîëå= { 0, 1, 2, 3, 4 }.F =F5 [x]/ñîäåðæèò òîëüêî ïîëèíîìû4è èõ ìíîãî÷ëåíx2 + x + 1 .x2 + x + 1 ∼= F25 ; îíî0-é è 1-é ñòåïåíåé èç F5 [x].1-é ñòåïåíè20 øò.Âñå ìíîãî÷ëåíûax + bF5íåïðèâîäèìû, èìåþò âèäÂñå ëè îíè ïðèìèòèâíûå ýëåìåíòû ïîëÿF?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà30 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂñåãäà ëè íåïðèâîäèìûé ìíîãî÷ëåí åñòü ïðèìèòèâíûéýëåìåíò?F51Âîçüì¼ì ïîëå2Âîçüì¼ì íåïðèâîäèìûé íàä3Ïîñòðîèì ïîëå= { 0, 1, 2, 3, 4 }.F =F5 [x]/ñîäåðæèò òîëüêî ïîëèíîìû4è èõ ìíîãî÷ëåííåïðèâîäèìû, èìåþò âèäÂñå ëè îíè ïðèìèòèâíûå ýëåìåíòû ïîëÿìíîãî÷ëåíûF?52 − 1 = 24êîòîðûõ ϕ(24) = 8 ïðèìèòèâíûõ ⇒ íå âñå1-é ñòåïåíè ãåíåðàòîðû ⇒Ìóëüòèïëèêàòèâíàÿ ãðóïïà ïîëÿýëåìåíòà èçx2 + x + 1 .x2 + x + 1 ∼= F25 ; îíî0-é è 1-é ñòåïåíåé èç F5 [x].1-é ñòåïåíè20 øò.Âñå ìíîãî÷ëåíûax + bF5îòâåò íà îáà âîïðîñà ÍÅÒ!FñîäåðæèòÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà31 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂñåãäà ëè íåïðèâîäèìûé ìíîãî÷ëåí åñòü ïðèìèòèâíûéýëåìåíò?...α= x íå åñòü2Óäîñòîâåðèìñÿ, ÷òîF =ÂF5 [x]/x +x+1ïðèìèòèâíûé ýëåìåíò ïîëÿ.F : x2 = −x − 1 = 4x + 4èα =xα2 = 4x + 4,α3 = 4x2 + 4x = 16x + 16 + 4x = 1.Èíòåðåñíûé (è âàæíûé!) âîïðîñ:êîãäà x åñòü ïðèìèòèâíûé ýëåìåíò ïîëÿFp [x]/(a(x))?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà32 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏðèìèòèâíûå ìíîãî÷ëåíûÂîïðîñx: êîãäà êîðåíüíåïðèâîäèìîãî íàäýëåìåíòîì ïîëÿFp(ñàì íåïðèâîäèìûé ìíîãî÷ëåí!)ìíîãî÷ëåíàFp [x]/(a(x))?a(x)áóäåò ïðèìèòèâíûìÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà32 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏðèìèòèâíûå ìíîãî÷ëåíûÂîïðîñx: êîãäà êîðåíüíåïðèâîäèìîãî íàäýëåìåíòîì ïîëÿÎòâåòFp(ñàì íåïðèâîäèìûé ìíîãî÷ëåí!)ìíîãî÷ëåíàFp [x]/(a(x))?a(x)áóäåò ïðèìèòèâíûì: ýòî áóäåò åñëè è òîëüêî åñëè ìíîãî÷ëåíïðèìèòèâåíïðè êîòîðîìx, ò.å.
m =a(x) | xm − 1.äëÿpn−1a(x) íàèìåíüøèé ïîêàçàòåëü,ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà32 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏðèìèòèâíûå ìíîãî÷ëåíûÂîïðîñx: êîãäà êîðåíüíåïðèâîäèìîãî íàäýëåìåíòîì ïîëÿÎòâåòFp(ñàì íåïðèâîäèìûé ìíîãî÷ëåí!)ìíîãî÷ëåíàFp [x]/(a(x))?a(x)áóäåò ïðèìèòèâíûì: ýòî áóäåò åñëè è òîëüêî åñëè ìíîãî÷ëåíïðèìèòèâåíïðè êîòîðîìx, ò.å. m =a(x) | xm − 1.äëÿpn−1a(x) íàèìåíüøèé ïîêàçàòåëü,Ïðèìåð¶ Íåïðèâîäèìûé íàä F2 ìíîãî÷ëåí x3 + x + 1 ïðèìèòèâåí:3x2 −1 − 1 = x7 + 1 = (x3 + x + 1) · (x4 + x2 + x + 1) è.xt − 1 6 .. x3 + x + 1F∗2 [x]/íè ïðè êàêîìx3 + x + 1 =1 6 t < 7 = m.Ïîýòîìóx0 = 1, x1 , x2 , x3 = x + 1,x4 = x2 + x, x5 = x2 + x + 1, x6 = x2 + 1.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà33 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏðèìèòèâíûå ìíîãî÷ëåíû...·Íåïðèâîäèìûé íàäF2ïðèìèòèâåí: îí äåëèò íå òîëüêîè áèíîìx4 + x3 + x2 + x + 1 íå24 −1 − 1 = x15 − 1, íîáèíîì xìíîãî÷ëåíx5 − 1:x5 − 1 = x5 + 1 = (x4 + x3 + x2 + x + 1) · (x + 1),èëè, ÷òî òîæå,deg x = 5 6= 15:x5 = (x4 + x3 + x2 + x + 1) · (x + 1) +1 = 1.|{z}=0ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏðèìèòèâíûå ìíîãî÷ëåíû: çàäà÷àÎïðåäåëèòü, ÿâëÿåòñÿ ëè íåïðèâîäèìûé ìíîãî÷ëåíf (x) = x6 + x3 + 1 ∈ F2 [x] ïðèìèòèâíûì?34 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà34 / 95Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏðèìèòèâíûå ìíîãî÷ëåíû: çàäà÷àÎïðåäåëèòü, ÿâëÿåòñÿ ëè íåïðèâîäèìûé ìíîãî÷ëåíf (x) = x6 + x3 + 1 ∈ F2 [x] ïðèìèòèâíûì?ÐåøåíèåÌóëüòèïëèêàòèâíàÿ ãðóïïà ïîëÿ26 − 1 = 63F2 [x]/ x6 + x3 + 1ñîñòîèò èçýëåìåíòîâ.d63 = 32· 7 ñóòü 3 è 7 ⇒ðàâåíñòâî x = 163äëÿ d ∈21 = 633 , 9= 7 .Ïðîñòûå äåëèòåëèíóæíî ïðîâåðèòü ðàññìàòðèâàåìîì ïîëåx6 = x3 + 1èx9 = x6 x3 = (x3 + 1)x3 = x6 + x3 = 6 x3 + 1+ 6 x3 = 1.Ò.î.deg x = 9 6= 63è ìíîãî÷ëåíf (x)íå ïðèìèòèâåí.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ ÃàëóàÂû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÐàçäåëû1234567Ïîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÂû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÂåêòîðíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåìÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ GF (pn)Öèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è ñ ðåøåíèÿìè35 / 95ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I. Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà36 / 95Âû÷èñëåíèå ýëåìåíòîâ â êîíå÷íûõ ïîëÿõÀëãîðèòì Åâêëèäà ïðèìåíÿþò äëÿ íàõîæäåíèÿ ÍÎÄ(a, b) íàòóðàëüíûõÍàáëþäåíèå(a, b),a > b).: îáùèé äåëèòåëü ïàðû ÷èñåëèì è äëÿ ïàðû(a − b, b)(ñ÷èòàåì, ÷òîaèb.òî îñòà¼òñÿÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü I.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
