Polinom véges mező felett

A véges mező feletti polinom $f(x)$ az alak formális összege $\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.

Itt van egy nem-negatív egész szám, amelyet a polinom fokának neveznek , és az algebra azon elemei , amelyek szorzását a szabályok megadják: $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.

Egy ilyen definíció lehetővé teszi a polinomok formális szorzását anélkül, hogy attól kellene tartani, hogy a véges mező ugyanazon elemének különböző fokai egybeeshetnek [1] [2] .

Egy véges mező felett bármely függvény megadható valamilyen polinom segítségével (például a Lagrange interpolációs polinom ).

Kapcsolódó definíciók

A számot a polinom fokának nevezzük , és [2] -ként jelöljük . $m\geqslant 0$ $\deg(f(x))$
Ha , akkor a polinomot normalizáltnak (redukáltnak) nevezzük [2] . Egy polinom mindig normalizálható, ha elosztjuk a legmagasabb fokú együtthatóval. $f_m=1$ $f_m$
A polinomok összegét és szorzatát a szokásos módon határozzuk meg, és az együtthatókkal végzett műveleteket a mezőben hajtjuk végre . $\mathbb {F} _{q}$
Két polinomhoz és mindig vannak polinomok és a mező felett úgy, hogy a reláció $f(x)$ $h(x)\ne 0$ $t(x)$ $r(x)$ $\mathbb {F} _{q}$ $f(x)=t(x)h(x)+r(x).$
- Ha a fok szigorúan kisebb, mint a fok , akkor egy ilyen relációt a polinom hányadosának és a -val való osztás maradékának ábrázolásának nevezzük , és az ilyen ábrázolás egyedi [3] . Nyilvánvaló, hogy maradék nélkül osztható -vel , amelyet a következővel írunk: [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)}$
- Ha , akkor a polinomot a polinom osztójának nevezzük [ 5 ] . $r(x)=0$ $h(x)$ $f(x)$
Egy polinom irreducibilis egy mező felett, ha nincs nem triviális osztója (0-nál nagyobb és ,-nál kisebb fok ) [5] [6] . $\mathbb {F} _{q}$ $\deg(f(x))$
A mezőkiterjesztés maradékosztályok halmaza , modulo egy mező feletti irreducibilis polinom [6] . $GF(q)$ $F[x]_{/(p(x))}$ $p(x)$ $GF(q)$
Egy kiterjesztett mezőből származó elem minimális polinomja (minimális függvénye) egy olyan normalizált polinom , amely minimális fokon [7] [8] . $\beta$ $m(x)$ $GF(q)$ $m(\béta)=0$
A polinom gyöke a mező bármely olyan eleme, amelyen ennek a polinomnak az értéke nulla.
A mező konjugált elemei azok, amelyek ugyanannak az irreducibilis polinomnak a gyökei [9] .

Polinom gyökök

Egy m fokú polinomnak pontosan m gyöke van (a multiplicitást számolva), amelyek valamely kiterjesztett mezőhöz tartoznak . Ha , hol a prím, akkor . A véges mezők tulajdonságai alapján a mező bármely eleme a binomiális gyöke : ${\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 )))

Így a polinom gyökerei egyben a binomiális gyökerei is [10] . $f(x)$ $x^Qx$

Bezout tétele és következményei érvényesek:

Az elosztás után a maradék . $f(x)$ $(xa)$ $f(a)$

Ha gyök , akkor oszt . $x_{0}$ $f(x)$ $(x-x_0)$ $f(x)$

Ha a lényeg a gyökerek , akkor $x_1,\;\ldots,\;x_m$ $f(x)$

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

A következő tételek is igazak:

1. tétel . Ha gyök , akkor gyök is [11] . $x_{0}$ $f(x)$ $x_0^q$ $f(x)$

2. Tétel . A Galois-mező konjugált elemei azonos sorrendűek [9] .

Cyclotomic osztály

Az 1. Tétel következménye lehet, hogy ha egy polinom gyöke a mező felett , akkor és annak gyökei. ${\displaystyle \alpha \in \mathbb {F} _{Q))$ $f(x)$ $\mathbb {F} _{q}$ $\alpha ^{q},\;\alpha ^{q^{2)),\;\alpha ^{q^{3)),\;\ldots \in \mathbb {F} _{Q }$

Definíció: Egy bizonyos elem által generált mező feletti ciklotómikus osztály az összes különálló elem halmaza, amely hatvány [12] . ${\displaystyle \mathbb {F} _{q},\;q=p^{s))$ ${\displaystyle \alpha \in \mathbb {F} _{Q},\;Q=p^{S))$ $\mathbb {F} _{Q}$ $q$ $\alpha$

Ha a mező primitív eleme [13] (olyan eleme, mint a ) , akkor a mező feletti ciklotomikus osztálynak pontosan lesznek elemei. $\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$

Megjegyzendő, hogy egy ciklotómikus osztály bármely eleme létrehozhatja ezt, és csak ezt az osztályt, következésképpen csak ehhez az osztályhoz tartozik.

Példák ciklotómikus osztályokra

Példa 1. Legyen , és a mező primitív eleme , azaz for . Figyelembe véve azt is , hogy a mező összes nullától eltérő elemét három ciklotómikus osztályra bonthatjuk a mezőn keresztül : $q=2$ $Q=2^3=8$ $\alpha$ $\mathbb {F} _{8}$ $\alpha^7=1$ $\alpha^i\neq 1$ $én <7$ $\alpha^8=\alpha$ $\mathbb {F} _{8}$ $\mathbb {F} _{2}$

\begin{mátrix} \{1\}, \\ \{\alpha,\;\alpha^2,\;\alpha^4\}, \\ \{\alpha^3,\;\alpha^6, \;\alpha^5\}. \end{mátrix}

2. példa Hasonlóképpen építhet osztályokat a mezőre a mező fölé , azaz . Legyen tehát a mező primitív eleme . $\mathbb {F} _{16}$ $\mathbb {F} _{4}$ $q=4,\;Q=q^2=16$ $\alpha$ $\mathbb {F} _{16}$ $\alpha^{15}=1,\;\alpha^{16}=\alpha$

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

Kapcsolat a polinomok gyökereivel

A következő tétel kapcsolatot létesít a ciklotómikus osztályok és egy polinom irreducibilis polinomokra való felbontása között egy mezőn keresztül . $x^{Q-1}-1$ $\mathbb {F} _{q}$

3. Tétel. Legyenek egy elem és egy polinom által generált ciklotomikus osztály gyökei ennek a ciklotómikus osztálynak az elemei, azaz. $\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}}).

Ekkor a polinom együtthatói a mezőben vannak , és maga a polinom irreducibilis ezen a területen. $f_0,\;f_1,\;\ldots,\;f_{m-1}$ $f(x)$ $\mathbb {F} _{q}$

A 3. Tételből megállapítható egy ilyen következmény . A véges mezők tulajdonságából, amely szerint a mező minden nem nulla eleme a polinom gyöke , arra a következtetésre juthatunk, hogy a polinom felbontható a mező felett irreducibilis polinomokra , amelyek mindegyike megfelel a saját ciklotomikus osztályának. [14] . $\mathbb {F} _{Q}$ $x^{Q-1}-1$ $x^{Q-1}-1$ $\mathbb {F} _{q}$ $f_0(x),\;f_1(x),\;\ldots,\;f_d$

A polinomok típusai

Primitív polinomok

Meghatározás . Egy irreducibilis polinom gyökeinek sorrendjét nevezzük annak a kitevőnek, amelyhez ez a polinom tartozik. Egy irreducibilis polinomot primitívnek nevezünk, ha minden gyöke a mező multiplikatív csoportjának generáló eleme [15] .

Egy primitív polinom minden gyökének sorrendje megegyezik a kiterjesztett mező multiplikatív csoportjának sorrendjével , azaz [11] . $\mathbb {F} _{Q}$ $Q-1$

Körpolinomok

Legyen a mező multiplikatív csoportjának generáló eleme, melynek sorrendje , azaz . Legyen a rend minden eleme a polinom gyöke . Ekkor egy ilyen polinomot körkörösnek nevezünk, és a [16] egyenlőség igaz : $\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)

Zhegalkin polinomok

A véges mezők feletti polinomok közül a Zhegalkin-polinomok különösen megkülönböztethetők . Ezek sok változó polinomjai a mezőben [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}

Egy ilyen polinom segítségével bármilyen logikai függvényt megadhatunk [18] , és egyedi módon [17] [19] . $f(x_{1},\;x_{2},\;\ldots ,\;x_{N})$

Alkalmazás

Sok olyan algoritmus létezik, amely véges mezők és gyűrűk felett polinomokat használ.

Valamint a véges mezők feletti polinomokat használják a modern hibajavító kódolásban [20] ( ciklikus kódok leírására [21] és a Reed-Solomon kód dekódolására az Euclid algoritmus [22] segítségével ), pszeudo-véletlenszám-generátorokban [23]. ( Shift regiszterekkel valósítva meg ) [24] , streaming titkosítással [25] és adatintegritás-ellenőrző algoritmusokkal.

Lásd még

Jegyzetek

↑ 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 Sagalovich, 2014 , p. 79.
↑ Sagalovich, 2014 , p. 93.
↑ Blahut, 1986 , p. 104.
↑ 1 2 Sagalovich, 2014 , p. 101.
↑ Sagalovich, 2014 , p. 82.
↑ 1 2 Sagalovich, 2014 , p. 96.
↑ Sagalovich, 2014 , p. 105.
↑ Blahut, 1986 , p. 99.
↑ Sagalovich, 2014 , p. 97.
↑ Blahut, 1986 , p. 103.
↑ Sagalovich, 2014 , p. 102.
↑ 1 2 Yablonsky, 1986 , p. 32.
↑ Yablonsky, 1986 , p. 12.
↑ Gabidulin, Ksevetszkij, Kolybelnikov, 2011 , p. 81.
↑ Sagalovich, 2014 , p. 169-172.
↑ Blahut, 1986 , p. 116-121.
↑ Blahut, 1986 , p. 223-228.
↑ Gabidulin, Ksevetszkij, Kolybelnikov, 2011 , p. 77-83.
↑ Alferov, Zubov, Kuzmin et al., 2005 , p. 251-260.
↑ Gabidulin, Ksevetszkij, Kolybelnikov, 2011 , p. 74-83.

Irodalom

Akritas A. A számítógépes algebra alapjai alkalmazásokkal / per. angolról. E. V. Pankratieva . — M .: Mir, 1994. — 544 p.
Alferov A. P. , Zubov A. Yu. , Kuzmin A. S. , Cheremushkin A. V. A kriptográfia alapjai : Tankönyv - 3. kiadás, Rev. és további - M . : Helios ARV , 2005. - 480 p. — ISBN 978-5-85438-137-6
Bleyhut R. E. A hibákat vezérlő kódok elmélete és gyakorlata / szerk. K. Sh. Zigangirova , ford. per. angolról. I. I. Grushko , V. M. Blinovsky - M .: Mir , 1986. - 576 p.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Információbiztonság : tankönyv - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Sagalovich Yu. L. Bevezetés az algebrai kódokba - 3. kiadás, átdolgozva. és további - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Yablonsky SV Bevezetés a diszkrét matematikába : Proc. egyetemi pótlék - 2. kiadás, átdolgozva. és további — M .: Nauka , 1986. — 384 p.
Peterson W., Weldon E. Hibajavító kódok. - M . : Mir, 1976. - S. 596.