Polynom nad konečným polem

Polynom nad konečným tělesem $f(x)$ je formální součet tvaru $\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.

Zde je nezáporné celé číslo, které se nazývá stupeň polynomu a jsou to prvky algebry , jejichž násobení je dáno pravidly: $m$ $f(x)$ $x^k, k\in \mathbb N_0$ $\mathbb {F} _{q},$

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

x^0 \ekviv 1.

Taková definice umožňuje formálně násobit polynomy, aniž by se museli obávat, že různé stupně stejného prvku konečného pole se mohou shodovat [1] [2] .

Jakákoli funkce nad konečným polem může být specifikována pomocí nějakého polynomu (jako je Lagrangeův interpolační polynom ).

Související definice

Číslo se nazývá stupeň polynomu a označuje se jako [2] . $m\geqslant 0$ $\deg(f(x))$
Jestliže , pak se polynom nazývá normalizovaný (redukovaný) [2] . Polynom lze vždy normalizovat jeho dělením koeficientem na nejvyšším stupni. $f_m=1$ $f_m$
Součet a součin polynomů se definují obvyklým způsobem a operace s koeficienty se provádějí v poli . $\mathbb {F} _{q}$
Pro dva polynomy a jsou vždy polynomy a nad polem takové, že vztah $f(x)$ $h(x)\ne 0$ $t(x)$ $r(x)$ $\mathbb {F} _{q}$ $f(x)=t(x)h(x)+r(x).$
- Pokud je stupeň přísně menší než stupeň , pak se takový vztah nazývá zobrazení polynomu jako kvocient a zbytek dělení podle , a takové zobrazení je jedinečné [3] . Je jasné, že je beze zbytku dělitelné , což se zapisuje jako [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)}$
- Jestliže , pak se polynom nazývá dělitel polynomu [5] . $r(x)=0$ $h(x)$ $f(x)$
Polynom je ireducibilní nad polem , pokud nemá žádné netriviální dělitele (stupně větší než 0 a menší než ) [5] [6] . $\mathbb {F} _{q}$ $\deg(f(x))$
Rozšíření pole je soubor tříd zbytků modulo neredukovatelný polynom nad polem [6] . $GF(q)$ $F[x]_{/(p(x))}$ $p(x)$ $GF(q)$
Minimální polynom (minimální funkce) pro prvek z rozšířeného pole je normalizovaný polynom přes minimální stupeň takový, že [7] [8] . $\beta$ $m(x)$ $GF(q)$ $m(\beta)=0$
Kořenem polynomu je libovolný prvek pole, na kterém je hodnota tohoto polynomu rovna nule.
Konjugované prvky pole jsou ty, které jsou kořeny stejného ireducibilního polynomu [9] .

Polynomiální kořeny

Polynom stupně m má přesně m kořenů (počítající násobnost), které patří do nějakého rozšířeného pole . Jestliže , kde je prvočíslo, pak . Na základě vlastností konečných těles je každý prvek pole kořenem binomu : ${\displaystyle \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$

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

Kořeny polynomu jsou tedy zároveň kořeny binomu [10] . $f(x)$ $x^Qx$

Bezoutova věta a její důsledky jsou platné:

Zbytek po dělení je . $f(x)$ $(xa)$ $f(a)$

Jestliže je kořen , pak dělí . $x_{0}$ $f(x)$ $(x-x_0)$ $f(x)$

Pokud jsou podstatou kořeny , pak $x_1,\;\ldots,\;x_m$ $f(x)$

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

Následující věty jsou také pravdivé:

Věta 1 . Jestliže je kořen , pak je také kořen [11] . $x_{0}$ $f(x)$ $x_0^q$ $f(x)$

Věta 2 . Konjugované prvky Galoisova pole mají stejné pořadí [9] .

Cyklotomická třída

Důsledkem věty 1 může být skutečnost, že jestliže je kořenem polynomu nad polem , pak a jsou jeho kořeny. ${\displaystyle \alpha \in \mathbb {F} _{Q))$ $f(x)$ $\mathbb {F} _{q}$ $\alpha ^{q},\;\alpha ^{q^{2)),\;\alpha ^{q^{3)),\;\ldots \in \mathbb {F} _{Q }$

Definice: Cyklotomická třída nad polem generovaným nějakým prvkem je množina všech odlišných prvků , které jsou mocninami [12] . $\mathbb {F} _{q},\;q=p^{s}$ ${\displaystyle \alpha \in \mathbb {F} _{Q},\;Q=p^{S))$ $\mathbb {F} _{Q}$ $q$ $\alpha$

Jestliže je primitivním prvkem [13] (např. prvek pro ) pole , pak cyklotomická třída nad polem bude mít přesně prvky. $\alpha$ $\alpha^{Q-1}=1$ $\alpha^k\neq 1$ $0<k<Q-1$ ${\displaystyle \mathbb {F} _{Q},\;Q=q^{m))$ $C=\{\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}\}$ $\mathbb {F} _{q}$ $m$

Je třeba poznamenat, že jakýkoli prvek z cyklotomické třídy může generovat tuto a pouze tuto třídu, a v důsledku toho patří pouze do ní.

Příklady cyklotomických tříd

Příklad 1. Dovolit , a být primitivní prvek pole , to je , pro . Uvážíme-li také , že můžeme získat rozklad všech nenulových prvků pole do tří cyklotomických tříd nad polem : $q=2$ $Q=2^3=8$ $\alpha$ $\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{matrix}

Příklad 2. Podobně můžete vytvořit třídy na poli nad polem , tedy . Nechť je primitivní prvek pole , tedy . $\mathbb {F} _{16}$ $\mathbb {F} _{4}$ $q=4,\;Q=q^2=16$ $\alpha$ $\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{matrix}

Spojení s kořeny polynomů

Následující věta zakládá spojení mezi cyklotomickými třídami a rozkladem polynomu na neredukovatelné polynomy nad polem . $x^{Q-1}-1$ $\mathbb {F} _{q}$

Věta 3. Nechť cyklotomická třída generovaná prvkem a polynomem má za kořeny prvky této cyklotomické třídy, tzn. $\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}}).

Pak koeficienty polynomu leží v poli a samotný polynom je nad tímto polem neredukovatelný. $f_0,\;f_1,\;\ldots,\;f_{m-1}$ $f(x)$ $\mathbb {F} _{q}$

Takový důsledek lze vytvořit z věty 3 . Z vlastnosti konečných těles, která říká, že všechny nenulové prvky tělesa jsou kořeny polynomu , můžeme usuzovat, že polynom lze rozložit na polynomy neredukovatelné přes pole , z nichž každý odpovídá své vlastní cyklotomické třídě. [14] . $\mathbb {F} _{Q}$ $x^{Q-1}-1$ $x^{Q-1}-1$ $\mathbb {F} _{q}$ $f_0(x),\;f_1(x),\;\ldots,\;f_d$

Typy polynomů

Primitivní polynomy

Definice . Pořadí kořenů ireducibilního polynomu se nazývá exponent, ke kterému tento polynom patří. Ireducibilní polynom se nazývá primitivní , pokud všechny jeho kořeny generují prvky multiplikativní grupy pole [15] .

Všechny kořeny primitivního polynomu mají řád rovný řádu multiplikativní grupy rozšířeného pole , tj. [11] . $\mathbb {F} _{Q}$ $Q-1$

Kruhové polynomy

Nechť existuje generující prvek multiplikativní grupy pole a jeho pořadí je , tj . Nechť všechny prvky řádu jsou kořeny polynomu . Pak se takový polynom nazývá kruhový a rovnost [16] je pravdivá : $\alpha$ $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)

Zhegalkinovy polynomy

Mezi polynomy nad konečnými tělesy se zvláště rozlišují Zhegalkinovy polynomy . Jsou to polynomy mnoha proměnných nad polem [17] . $GF(2)$

f(x_{1},\;x_{2},\;\ldots ,\;x_{N})=a+\sum _{1\leqslant i\leqslant N}a_{i}x_{i }+\součet _{1\leqslant i<j\leqslant N}a_{i,j}x_{i}x_{j}+\součet _{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}

Pomocí takového polynomu můžete zadat libovolnou booleovskou funkci [18] , a to jedinečným způsobem [17] [19] . $f(x_{1},\;x_{2},\;\ldots ,\;x_{N})$

Aplikace

Existuje mnoho algoritmů, které používají polynomy nad konečnými poli a kruhy.

Také polynomy nad konečnými poli se používají v moderním kódování pro opravu chyb [20] (pro popis cyklických kódů [21] a pro dekódování Reed-Solomonova kódu pomocí Euklidova algoritmu [22] ), generátory pseudonáhodných čísel [23] (implementováno pomocí posuvných registrů ) [24] , šifrování streamování [25] a algoritmy kontroly integrity dat.

Viz také

Poznámky

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

Literatura

Akritas A. Základy počítačové algebry s aplikacemi / per. z angličtiny. E. V. Pankratieva . — M .: Mir, 1994. — 544 s.
Alferov A. P. , Zubov A. Yu. , Kuzmin A. S. , Cheremushkin A. V. Základy kryptografie : Učebnice - 3. vyd., Rev. a doplňkové - M .: Helios ARV , 2005. - 480 s. — ISBN 978-5-85438-137-6
Bleyhut R. E. Teorie a praxe kódů, které kontrolují chyby / ed. K. Sh. Zigangirova , přel. za. z angličtiny. I.I. Grushko , V. M. Blinovsky - M .: Mir , 1986. - 576 s.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informační bezpečnost : učebnice - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Sagalovich Yu.L. Úvod do algebraických kódů - 3. vydání, revidováno. a doplňkové - M. : IPPI RAN , 2014. - 310 s. — ISBN 978-5-901158-24-1
Yablonsky SV Úvod do diskrétní matematiky : Proc. příspěvek pro vysoké školy - 2. vyd., revid. a doplňkové — M .: Nauka , 1986. — 384 s.
Peterson W., Weldon E. Kódy pro opravu chyb. - M .: Mir, 1976. - S. 596.