Polynomium over begrænset felt

Et polynomium over et begrænset felt $f(x)$ er en formel sum af formen $\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.

Her er et ikke-negativt heltal, kaldet graden af polynomiet , og er de elementer i algebraen , hvis multiplikation er givet af reglerne: $m$ $f(x)$ $x^k, k\in \mathbb N_0$ $\mathbb {F} _{q},$

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

x^0 \ækvivalent 1.

En sådan definition gør det muligt at multiplicere polynomier formelt uden at bekymre sig om, at forskellige grader af det samme element i det endelige felt kan falde sammen [1] [2] .

Enhver funktion over et begrænset felt kan specificeres ved hjælp af et eller andet polynomium (såsom Lagrange-interpolationspolynomiet ).

Relaterede definitioner

Tallet kaldes polynomiets grad og betegnes som [2] . $m\geqslant 0$ $\grader(f(x))$
Hvis , så kaldes polynomiet normaliseret (reduceret) [2] . Et polynomium kan altid normaliseres ved at dividere det med koefficienten i højeste grad. $f_m=1$ $f_m$
Summen og produktet af polynomier defineres på sædvanlig måde, og operationer med koefficienter udføres i feltet . $\mathbb {F} _{q}$
For to polynomier og der er altid polynomier og over feltet sådan, at relationen $f(x)$ $h(x)\ne 0$ $t(x)$ $r(x)$ $\mathbb {F} _{q}$ $f(x)=t(x)h(x)+r(x).$
- Hvis graden er strengt taget mindre end graden , så kaldes en sådan relation repræsentationen af polynomiet som en kvotient og resten af division med , og en sådan repræsentation er unik [3] . Det er klart, at er deleligt uden rest med , som er skrevet som [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)}$
- Hvis , så kaldes polynomiet divisor af polynomiet [5] . $r(x)=0$ $h(x)$ $f(x)$
Et polynomium er irreducerbart over et felt, hvis det ikke har nogen ikke-trivielle divisorer (grader større end 0 og mindre end ) [5] [6] . $\mathbb {F} _{q}$ $\grader(f(x))$
En feltudvidelse er et sæt af restklasser modulo et irreducerbart polynomium over et felt [6] . $GF(q)$ $F[x]_{/(p(x))}$ $p(x)$ $GF(q)$
Et minimalt polynomium (minimal funktion) for et element fra et udvidet felt er et normaliseret polynomium over minimal grad, således at [7] [8] . $\beta$ $m(x)$ $GF(q)$ $m(\beta)=0$
Roden af et polynomium er et hvilket som helst element i feltet, hvor værdien af dette polynomium er lig nul.
Konjugerede elementer i feltet er dem, der er rødder til det samme irreducerbare polynomium [9] .

Polynomiske rødder

Et polynomium af grad m har præcis m rødder (tæller multiplicitet), der hører til et eller andet udvidet felt . Hvis , hvor er prime, så . Baseret på egenskaberne af endelige felter er ethvert element i feltet roden af binomialet : ${\displaystyle \mathbb {F} _{Q},\quad \mathbb {F} _{q}\subseteq \mathbb {F} _{Q))$ $q=p^s$ $s$ $Q=p^S,\;S\geqslant s$ $\mathbb {F} _{Q}$ $x^Qx$

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

Således er rødderne af et polynomium også rødderne af et binomium [10] . $f(x)$ $x^Qx$

Bezouts sætning og dens følger er gyldige:

Resten efter at dividere med er . $f(x)$ $(xa)$ $f(a)$

Hvis er en rod , så divideres . $x_{0}$ $f(x)$ $(x-x_0)$ $f(x)$

Hvis essensen er rødder , så $x_1,\;\ldots,\;x_m$ $f(x)$

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

Følgende teoremer er også sande:

Sætning 1 . Hvis er en rod , så er det også en rod [11] . $x_{0}$ $f(x)$ $x_0^q$ $f(x)$

Sætning 2 . De konjugerede elementer i Galois-feltet har samme rækkefølge [9] .

Cyklotomisk klasse

En konsekvens af sætning 1 kan være det faktum, at hvis er en rod af et polynomium over feltet , så er og dets rødder. ${\displaystyle \alpha \in \mathbb {F} _{Q))$ $f(x)$ $\mathbb {F} _{q}$ $\alpha ^{q},\;\alpha ^{q^{2)),\;\alpha ^{q^{3)),\;\ldots \i \mathbb {F} _{Q }$

Definition: En cyklotomisk klasse over et felt genereret af et eller andet element er mængden af alle distinkte elementer , der er th potenser [12] . ${\displaystyle \mathbb {F} _{q},\;q=p^{s))$ ${\displaystyle \alpha \in \mathbb {F} _{Q},\;Q=p^{S))$ $\mathbb {F} _{Q}$ $q$ $\alfa$

Hvis er et primitivt element [13] (sådan et element som for ) af feltet , så vil den cyklotomiske klasse over feltet have præcis elementer. $\alfa$ $\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$

Det skal bemærkes, at ethvert element fra en cyklotomisk klasse kan generere denne og kun denne klasse og følgelig kun tilhører den.

Eksempler på cyklotomiske klasser

Eksempel 1. Lad , og vær et primitivt element i feltet , det vil sige for . I betragtning af det , kan vi opnå en nedbrydning af alle ikke-nul elementer i feltet i tre cyklotomiske klasser over feltet : $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{matrix}

Eksempel 2. På samme måde kan du bygge klasser på feltet over feltet , det vil sige . Lad være et primitivt element i feltet , derfor . $\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{matrix}

Forbindelse med rødderne af polynomier

Følgende sætning etablerer en forbindelse mellem cyklotomiske klasser og nedbrydningen af et polynomium til irreducerbare polynomier over et felt . $x^{Q-1}-1$ $\mathbb {F} _{q}$

Sætning 3. Lad den cyklotomiske klasse genereret af et grundstof og et polynomium have elementer af denne cyklotomiske klasse som sine rødder, dvs. $\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}}).

Så ligger polynomiets koefficienter i feltet , og selve polynomiet er irreducerbart over dette felt. $f_0,\;f_1,\;\ldots,\;f_{m-1}$ $f(x)$ $\mathbb {F} _{q}$

Man kan fastslå en sådan følge af sætning 3 . Fra egenskaben af endelige felter, som siger, at alle ikke-nul elementer i feltet er rødderne af polynomiet , kan vi konkludere, at polynomiet kan dekomponeres i polynomier , der er irreducable over feltet , som hver svarer til sin egen cyklotomiske klasse [14] . $\mathbb {F} _{Q}$ $x^{Q-1}-1$ $x^{Q-1}-1$ $\mathbb {F} _{q}$ $f_0(x),\;f_1(x),\;\ldots,\;f_d$

Typer af polynomier

Primitive polynomier

Definition . Rækkefølgen af rødderne af et irreducerbart polynomium kaldes den eksponent, som dette polynomium tilhører. Et irreducerbart polynomium kaldes primitivt , hvis alle dets rødder genererer elementer af feltets multiplikative gruppe [15] .

Alle rødder af et primitivt polynomium har en rækkefølge, der er lig med rækkefølgen af multiplikationsgruppen i det udvidede felt , dvs. [11] . $\mathbb {F} _{Q}$ $Q-1$

Cirkelpolynomier

Lad der være et genererende element i feltets multiplikative gruppe , og dets rækkefølge er , dvs. Lad alle elementer i rækkefølgen være polynomiets rødder . Så kaldes et sådant polynomium cirkulært , og ligheden [16] er sand : $\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)

Zhegalkin polynomier

Blandt polynomier over endelige felter er Zhegalkin-polynomier særligt kendetegnet . De er polynomier af mange variable over feltet [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}

Ved at bruge et sådant polynomium kan du angive en hvilken som helst boolsk funktion [18] , og på en unik måde [17] [19] . $f(x_{1},\;x_{2},\;\ldots ,\;x_{N})$

Ansøgning

Der er mange algoritmer, der bruger polynomier over endelige felter og ringe.

Polynomier over endelige felter bruges også i moderne fejlkorrigerende kodning [20] (til beskrivelse af cykliske koder [21] og til afkodning af Reed-Solomon-koden ved hjælp af Euclid-algoritmen [22] ), pseudo-tilfældige talgeneratorer [23] (implementeret ved hjælp af skiftregistre ) [24] , streamingkryptering [25] og algoritmer til kontrol af dataintegritet.

Se også

Noter

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

Litteratur

Akritas A. Grundlæggende om computeralgebra med applikationer / pr. fra engelsk. E. V. Pankratieva . — M .: Mir, 1994. — 544 s.
Alferov A. P. , Zubov A. Yu. , Kuzmin A. S. , Cheremushkin A. V. Fundamentals of cryptography : Lærebog - 3. udgave, Rev. og yderligere - M . : Helios ARV , 2005. - 480 s. — ISBN 978-5-85438-137-6
Bleyhut R. E. Teori og praksis for koder, der kontrollerer fejl / red. K. Sh. Zigangirova , oversættelse. om. fra engelsk. I.I. Grushko , V. M. Blinovsky - M .: Mir , 1986. - 576 s.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informationssikkerhed : lærebog - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Sagalovich Yu. L. Introduktion til algebraiske koder - 3. udgave, revideret. og yderligere - M. : IPPI RAN , 2014. - 310 s. — ISBN 978-5-901158-24-1
Yablonsky SV Introduktion til diskret matematik : Proc. godtgørelse til universiteter - 2. udg., revideret. og yderligere — M .: Nauka , 1986. — 384 s.
Peterson W., Weldon E. Fejlkorrigerende koder. - M . : Mir, 1976. - S. 596.