Polinom peste câmp finit

Un polinom peste un câmp finit $f(x)$ este o sumă formală a formei $\mathbb {F} _{q}$

f(x)=f_{0}+f_{1}x+\ldots +f_{m}x^{m},\quad f_{i}\in \mathbb {F} _{q},\ quad f_{m}\neq 0.

Iată un număr întreg nenegativ, numit gradul polinomului și sunt elementele algebrei a căror înmulțire este dată de reguli: $m$ $f(x)$ $x^k, k\in \mathbb N_0$ $\mathbb {F} _{q},$

x^k \cdot x^m = x^{k+m},

x^0 \equiv 1.

O astfel de definiție permite înmulțirea formală a polinoamelor, fără a vă îngrijora că pot coincide grade diferite ale aceluiași element al câmpului finit [1] [2] .

Orice funcție dintr-un câmp finit poate fi specificată folosind un polinom (cum ar fi polinomul de interpolare Lagrange ).

Definiții înrudite

Numărul se numește gradul polinomului și se notează cu [2] . $m\geqslant 0$ $\deg(f(x))$
Dacă , atunci polinomul se numește normalizat (redus) [2] . Un polinom poate fi întotdeauna normalizat prin împărțirea lui la coeficientul de cel mai înalt grad. $f_m=1$ $f_m$
Suma și produsul polinoamelor sunt definite în mod obișnuit, iar operațiile cu coeficienți sunt efectuate în câmpul . $\mathbb {F} _{q}$
Pentru două polinoame și există întotdeauna polinoame și peste câmp astfel încât relația $f(x)$ $h(x)\ne 0$ $t(x)$ $r(x)$ $\mathbb {F} _{q}$ $f(x)=t(x)h(x)+r(x).$
- Dacă gradul este strict mai mic decât gradul , atunci o astfel de relație se numește reprezentarea polinomului ca cât și restul împărțirii cu , iar o astfel de reprezentare este unică [3] . Este clar că este divizibil fără rest cu , care se scrie ca [4] . $r(x)$ $h(x)$ $f(x)$ $f(x)$ $h(x)$ $f(x)-r(x)$ $h(x)$ $f(x)\equiv r(x)\pmod{h(x)}$
- Dacă , atunci polinomul se numește divizor al polinomului [5] . $r(x)=0$ $h(x)$ $f(x)$
Un polinom este ireductibil peste un câmp dacă nu are divizori netriviali (grade mai mari decât 0 și mai mici decât ) [5] [6] . $\mathbb {F} _{q}$ $\deg(f(x))$
O extensie de câmp este un set de clase de reziduuri modulo un polinom ireductibil peste un câmp [6] . $GF(q)$ $F[x]_{/(p(x))}$ $p(x)$ $GF(q)$
Un polinom minim (funcție minimă) pentru un element dintr-un câmp extins este un polinom normalizat pe un grad minim astfel încât [7] [8] . $\beta$ $m(x)$ $GF(q)$ $m(\beta)=0$
Rădăcina unui polinom este orice element al câmpului, valoarea acestui polinom pe care este egală cu zero.
Elementele conjugate ale câmpului sunt cele care sunt rădăcini ale aceluiași polinom ireductibil [9] .

Rădăcini polinomiale

Un polinom de gradul m are exact m rădăcini (multiplicitatea numărării) care aparțin unui câmp extins . Dacă , unde este prim, atunci . Pe baza proprietăților câmpurilor finite, orice element al câmpului este rădăcina binomului : $\mathbb {F} _{Q},\quad \mathbb {F} _{q}\subseteq \mathbb {F} _{Q)$ $q=p^s$ $p$ $Q=p^S,\;S\geqslant s$ $\mathbb {F} _{Q}$ $x^Qx$

x^{Q}-x=\prod _{\alpha \in \mathbb {F} _{Q}}{(x-\alpha ))

Astfel, rădăcinile unui polinom sunt și rădăcinile unui binom [10] . $f(x)$ $x^Qx$

Teorema lui Bezout și corolarele sale sunt valabile:

Restul după împărțirea la este . $f(x)$ $(xa)$ $fa)$

Dacă este o rădăcină , atunci se împarte . $x_{0}$ $f(x)$ $(x-x_0)$ $f(x)$

Dacă esența sunt rădăcini , atunci $x_1,\;\ldots,\;x_m$ $f(x)$

f(x) = a(x-x_1)(x-x_2)\ldots(x-x_m).

Următoarele teoreme sunt de asemenea adevărate:

Teorema 1 . Dacă este o rădăcină , atunci este și o rădăcină [11] . $x_{0}$ $f(x)$ $x_0^q$ $f(x)$

Teorema 2 . Elementele conjugate ale câmpului Galois au aceeași ordine [9] .

Clasa ciclotomică

O consecință a teoremei 1 poate fi faptul că dacă este o rădăcină a unui polinom peste câmpul , atunci și sunt rădăcinile sale. $\alpha \in \mathbb {F} _{Q)$ $f(x)$ $\mathbb {F} _{q}$ $\alpha ^{q},\;\alpha ^{q^{2)),\;\alpha ^{q^{3)),\;\ldots \in \mathbb {F} _{Q }$

Definiție: O clasă ciclotomică peste un câmp generat de un element este mulțimea tuturor elementelor distincte care sunt puterile -alea [12] . $\mathbb {F} _{q},\;q=p^{s}$ $\alpha \in \mathbb {F} _{Q},\;Q=p^{S)$ $\mathbb {F} _{Q}$ $q$ $\alfa$

Dacă este un element primitiv [13] (un element ca pentru ) al câmpului , atunci clasa ciclotomică peste câmp va avea exact elemente. $\alfa$ $\alpha^{Q-1}=1$ $\alpha^k\neq 1$ $0<k<Q-1$ $\mathbb {F} _{Q},\;Q=q^{m)$ $C=\{\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}\}$ $\mathbb {F} _{q}$ $m$

De remarcat că orice element dintr-o clasă ciclotomică poate genera aceasta și numai această clasă și, în consecință, aparține numai acesteia.

Exemple de clase ciclotomice

Exemplul 1. Fie , și un element primitiv al câmpului , adică , pentru . Având în vedere, de asemenea , că putem obține o descompunere a tuturor elementelor nenule ale câmpului în trei clase ciclotomice pe câmp : $q=2$ $Q=2^3=8$ $\alfa$ $\mathbb {F} _{8}$ $\alpha^7=1$ $\alpha^i\neq 1$ $i<7$ $\alpha^8=\alpha$ $\mathbb {F} _{8}$ $\mathbb {F} _{2}$

\begin{matrix} \{1\}, \\ \{\alpha,\;\alpha^2,\;\alpha^4\}, \\ \{\alpha^3,\;\alpha^6, \;\alpha^5\}. \end{matrice}

Exemplul 2. În mod similar, puteți construi clase pe câmp peste câmpul , adică . Fie un element primitiv al câmpului , prin urmare . $\mathbb {F} _{16}$ $\mathbb {F} _{4}$ $q=4,\;Q=q^2=16$ $\alfa$ $\mathbb {F} _{16}$ $\alpha^{15}=1,\;\alpha^{16}=\alpha$

\begin{matrix} \{1\}, \\ \{\alpha,\;\alpha^4\},\;\{\alpha^2,\;\alpha^8\}, \\ \{\ alpha^3,\;\alpha^{12}\},\;\{\alpha^5\},\;\{\alpha^{10}\}, \\ \{\alpha^6,\; \alpha^9\},\;\{\alpha^7,\;\alpha^{13}\}, \\ \{\alpha^{11},\;\alpha^{14}\}. \end{matrice}

Legătura cu rădăcinile polinoamelor

Următoarea teoremă stabilește o legătură între clasele ciclotomice și descompunerea unui polinom în polinoame ireductibile pe un câmp . $x^{Q-1}-1$ $\mathbb {F} _{q}$

Teorema 3. Fie clasa ciclotomică generată de un element și un polinom să aibă drept rădăcini elemente din această clasă ciclotomică, i.e. $\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}$ $\alpha \in \mathbb {F} _{q^{l)}$ $f(x)=f_0+f_1 x+f_2 x^2+\ldots+f_{m-1}x^{m-1}+x^m$

f(x)=(x-\alpha)(x-\alpha^q)\ldots(x-\alpha^{q^{m-1}}).

Atunci coeficienții polinomului se află în câmpul , iar polinomul însuși este ireductibil în acest câmp. $f_0,\;f_1,\;\ldots,\;f_{m-1}$ $f(x)$ $\mathbb {F} _{q}$

Se poate stabili un astfel de corolar din Teorema 3 . Din proprietatea câmpurilor finite, care spune că toate elementele non-nule ale câmpului sunt rădăcinile polinomului , putem concluziona că polinomul poate fi descompus în polinoame ireductibile peste câmpul , fiecare dintre ele corespunde clasei sale ciclotomice. [14] . $\mathbb {F} _{Q}$ $x^{Q-1}-1$ $x^{Q-1}-1$ $\mathbb {F} _{q}$ $f_0(x),\;f_1(x),\;\ldots,\;f_d$

Tipuri de polinoame

Polinoame primitive

Definiție . Ordinea rădăcinilor unui polinom ireductibil se numește exponentul căruia îi aparține acest polinom. Un polinom ireductibil se numește primitiv dacă toate rădăcinile sale sunt elemente generatoare ale grupului multiplicativ al câmpului [15] .

Toate rădăcinile unui polinom primitiv au o ordine egală cu ordinea grupului multiplicativ al câmpului extins , adică [11] . $\mathbb {F} _{Q}$ $Q-1$

Polinoame în cerc

Să existe un element generator al grupului multiplicativ al câmpului , iar ordinea lui este , adică . Fie toate elementele ordinului rădăcinile polinomului . Atunci un astfel de polinom se numește circular și egalitatea [16] este adevărată : $\alfa$ $GF(q^{m})$ $n=q^{m}-1$ $\alpha^{q^m-1}=1$ $d$ $\psi _{d}(x),\;n\,\vdots \,d$

x^{q^{m}-1}-1=\prod _{d\,\mid \,q^{m}-1}\psi _{d}(x)

Polinoame Zhegalkin

Dintre polinoamele peste câmpuri finite, polinoamele Zhegalkin se disting în special . Sunt polinoame ale multor variabile din câmpul [17] . $GF(2)$

f(x_{1},\;x_{2},\;\ldots ,\;x_{N})=a+\sum _{1\leqslant i\leqslant N}a_{i}x_{i }+\sum _{1\leqslant i<j\leqslant N}a_{i,j}x_{i}x_{j}+\sum _{1\leqslant i<j<k\leqslant N}a_{i ,\;j,\;k}x_{i}x_{j}x_{k}+\ldots +a_{1,\;2,\;\ldots ,\;N}x_{1}x_{2} \ldots x_{N}

Folosind un astfel de polinom, puteți specifica orice funcție booleană [18] , și într-un mod unic [17] [19] . $f(x_{1},\;x_{2},\;\ldots ,\;x_{N})$

Aplicație

Există mulți algoritmi care folosesc polinoame peste câmpuri și inele finite.

De asemenea, polinoamele peste câmpuri finite sunt folosite în codificarea modernă de corectare a erorilor [20] (pentru descrierea codurilor ciclice [21] și pentru decodarea codului Reed-Solomon folosind algoritmul Euclid [22] ), generatoare de numere pseudoaleatoare [23] (implementat folosind registre de deplasare ) [24] , criptare în flux [25] și algoritmi de verificare a integrității datelor.

Vezi și

Note

↑ Akritas, 1994 , p. 146.
↑ 1 2 3 Blahut, 1986 , p. 88.
↑ Blahut, 1986 , p. 90.
↑ Blahut, 1986 , p. 91.
↑ 1 2 Blahut, 1986 , p. 89.
↑ 1 2 Sagalovici, 2014 , p. 79.
↑ Sagalovici, 2014 , p. 93.
↑ Blahut, 1986 , p. 104.
↑ 1 2 Sagalovici, 2014 , p. 101.
↑ Sagalovici, 2014 , p. 82.
↑ 1 2 Sagalovici, 2014 , p. 96.
↑ Sagalovici, 2014 , p. 105.
↑ Blahut, 1986 , p. 99.
↑ Sagalovici, 2014 , p. 97.
↑ Blahut, 1986 , p. 103.
↑ Sagalovici, 2014 , p. 102.
↑ 1 2 Yablonsky, 1986 , p. 32.
↑ Yablonsky, 1986 , p. 12.
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , p. 81.
↑ Sagalovici, 2014 , p. 169-172.
↑ Blahut, 1986 , p. 116-121.
↑ Blahut, 1986 , p. 223-228.
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , p. 77-83.
↑ Alferov, Zubov, Kuzmin et al., 2005 , p. 251-260.
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 , p. 74-83.

Literatură

Akritas A. Fundamentele algebrei computerizate cu aplicații / per. din engleza. E. V. Pankratieva . — M .: Mir, 1994. — 544 p.
Alferov A. P. , Zubov A. Yu. , Kuzmin A. S. , Cheremushkin A. V. Fundamentele criptografiei : Manual - ed. a 3-a, Rev. si suplimentare - M . : Helios ARV , 2005. - 480 p. — ISBN 978-5-85438-137-6
Bleyhut R. E. Teoria și practica codurilor care controlează erorile / ed. K. Sh. Zigangirova , trad. pe. din engleza. I.I. Grushko , V. M. Blinovsky - M .: Mir , 1986. - 576 p.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Securitatea informației : manual - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Sagalovici Yu. L. Introducere în codurile algebrice - ed. a 3-a, revizuită. si suplimentare - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Yablonsky SV Introducere în matematica discretă : Proc. indemnizație pentru universități - ed. a II-a, revizuită. si suplimentare — M .: Nauka , 1986. — 384 p.
Peterson W., Weldon E. Coduri de corectare a erorilor. - M . : Mir, 1976. - S. 596.