Polinomio sobre campo finito

Un polinomio sobre un campo finito $f(x)$ es una suma formal de la forma $\mathbb {F} _{q}$

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

Aquí hay un número entero no negativo, llamado grado del polinomio , y son los elementos del álgebra sobre cuya multiplicación viene dada por las reglas: $metro$ $f(x)$ $x^k, k\en \mathbb N_0$ $\mathbb {F} _{q},$

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

x^0 \equiv 1.

Tal definición permite multiplicar polinomios formalmente, sin preocuparse de que diferentes grados del mismo elemento del campo finito puedan coincidir [1] [2] .

Cualquier función sobre un campo finito se puede especificar usando algún polinomio (como el polinomio de interpolación de Lagrange ).

Definiciones relacionadas

El número se llama el grado del polinomio y se denota como [2] . $m\geqslant 0$ $\grado(f(x))$
Si , entonces el polinomio se llama normalizado (reducido) [2] . Un polinomio siempre se puede normalizar dividiéndolo por el coeficiente de mayor grado. $f_m=1$ $f_m$
La suma y el producto de polinomios se definen de la forma habitual, y las operaciones con coeficientes se realizan en el campo . $\mathbb {F} _{q}$
Para dos polinomios y siempre hay polinomios y sobre el campo tal que la relación $f(x)$ $h(x)\ne 0$ $t(x)$ $r(x)$ $\mathbb {F} _{q}$ $f(x)=t(x)h(x)+r(x).$
- Si el grado es estrictamente menor que el grado , entonces tal relación se denomina representación del polinomio como cociente y resto de la división por , y tal representación es única [3] . Es claro que es divisible sin resto por , que se escribe como [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)}$
- Si , entonces el polinomio se llama divisor del polinomio [5] . $r(x)=0$ $h(x)$ $f(x)$
Un polinomio es irreducible sobre un campo si no tiene divisores no triviales (grados mayores que 0 y menores que ) [5] [6] . $\mathbb {F} _{q}$ $\grado(f(x))$
Una extensión de campo es un conjunto de clases de residuos módulo un polinomio irreducible sobre un campo [6] . $FG(q)$ $F[x]_{/(p(x))}$ $p(x)$ $FG(q)$
Un polinomio mínimo (función mínima) para un elemento de un campo extendido es un polinomio normalizado sobre un grado mínimo tal que [7] [8] . $\beta$ $m(x)$ $FG(q)$ $m(\beta)=0$
La raíz de un polinomio es cualquier elemento del campo, el valor de este polinomio en el que es igual a cero.
Los elementos conjugados del campo son aquellos que son raíces de un mismo polinomio irreducible [9] .

Raíces de polinomios

Un polinomio de grado m tiene exactamente m raíces (contando la multiplicidad) que pertenecen a algún campo extendido . Si , donde es primo, entonces . Según las propiedades de los campos finitos, cualquier elemento del campo es la raíz del binomio : ${\displaystyle \mathbb {F}_{Q},\quad \mathbb {F}_{q}\subseteq \mathbb {F}_{Q})$ $q=p^s$ $pags$ $Q=p^S,\;S\geqslant s$ ${\ estilo de visualización \ mathbb {F} _ {Q}}$ $x^Qx$

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

Así, las raíces de un polinomio son también las raíces de un binomio [10] . $f(x)$ $x^Qx$

El teorema de Bezout y sus corolarios son válidos:

El resto después de dividir por es . $f(x)$ $(xa)$ $fa)$

Si es una raíz , entonces divide . $x_{0}$ $f(x)$ $(x-x_0)$ $f(x)$

Si la esencia son las raíces , entonces $x_1,\;\ldots,\;x_m$ $f(x)$

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

Los siguientes teoremas también son verdaderos:

Teorema 1 . Si es una raíz , entonces también es una raíz [11] . $x_{0}$ $f(x)$ $x_0^q$ $f(x)$

Teorema 2 . Los elementos conjugados del campo de Galois tienen el mismo orden [9] .

Clase ciclotómica

Una consecuencia del Teorema 1 puede ser el hecho de que si es una raíz de un polinomio sobre el campo , entonces y son sus raíces. ${\ estilo de visualización \ alfa \ en \ mathbb {F} _ {Q}}$ $f(x)$ $\mathbb {F} _{q}$ $\alpha ^{q},\;\alpha ^{q^{2)),\;\alpha ^{q^{3)),\;\ldots \in \mathbb {F}_{Q }$

Definición: Una clase ciclotómica sobre un campo generado por algún elemento es el conjunto de todos los elementos distintos que son las potencias [12] . ${\displaystyle \mathbb {F}_{q},\;q=p^{s))$ ${\displaystyle \alpha \in \mathbb {F} _{Q},\;Q=p^{S))$ ${\ estilo de visualización \ mathbb {F} _ {Q}}$ $q$ $\alfa$

Si es un elemento primitivo [13] (un elemento como para ) del campo , entonces la clase ciclotómica sobre el campo tendrá exactamente elementos. $\alfa$ $\alpha^{Q-1}=1$ $\alpha^k\neq 1$ $0<k<Q-1$ ${\displaystyle \mathbb {F}_{Q},\;Q=q^{m))$ $C=\{\alfa,\;\alfa^q,\;\alfa^{q^2},\;\ldots,\;\alfa^{q^{m-1}}\}$ $\mathbb {F} _{q}$ $metro$

Cabe señalar que cualquier elemento de una clase ciclotómica puede generar esta y solo esta clase y, en consecuencia, pertenecer solo a ella.

Ejemplos de clases ciclotómicas

Ejemplo 1. Sea , y un elemento primitivo del campo , es decir , para . Considerando también que podemos obtener una descomposición de todos los elementos distintos de cero del campo en tres clases ciclotómicas sobre el campo : $q=2$ $Q=2^3=8$ $\alfa$ ${\ estilo de visualización \ mathbb {F} _ {8}}$ $\alpha^7=1$ $\alpha^i\neq 1$ $yo<7$ $\alpha^8=\alfa$ ${\ estilo de visualización \ mathbb {F} _ {8}}$ $\mathbb {F} _{2}$

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

Ejemplo 2. De manera similar, puede construir clases en el campo sobre el campo , es decir, . Sea un elemento primitivo del campo , por lo tanto . ${\ estilo de visualización \ mathbb {F} _ {16}}$ $\mathbb {F} _{4}$ $q=4,\;Q=q^2=16$ $\alfa$ ${\ estilo de visualización \ mathbb {F} _ {16}}$ $\alpha^{15}=1,\;\alpha^{16}=\alfa$

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

Conexión con las raíces de polinomios

El siguiente teorema establece una conexión entre las clases ciclotómicas y la descomposición de un polinomio en polinomios irreducibles sobre un campo . $x^{Q-1}-1$ $\mathbb {F} _{q}$

Teorema 3. Sea la clase ciclotómica generada por un elemento y un polinomio que tenga como raíces elementos de esta clase ciclotómica, es decir $\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}$ ${\ estilo de visualización \ alfa \ en \ 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}}).

Entonces los coeficientes del polinomio se encuentran en el campo , y el polinomio mismo es irreducible sobre este campo. $f_0,\;f_1,\;\ldots,\;f_{m-1}$ $f(x)$ $\mathbb {F} _{q}$

Uno puede establecer tal corolario del Teorema 3 . De la propiedad de los campos finitos, que dice que todos los elementos distintos de cero del campo son las raíces del polinomio , podemos concluir que el polinomio se puede descomponer en polinomios irreducibles sobre el campo , cada uno de los cuales corresponde a su propia clase ciclotómica [14] . ${\ estilo de visualización \ mathbb {F} _ {Q}}$ $x^{Q-1}-1$ $x^{Q-1}-1$ $\mathbb {F} _{q}$ $f_0(x),\;f_1(x),\;\ldots,\;f_d$

Tipos de polinomios

Polinomios primitivos

Definición . El orden de las raíces de un polinomio irreducible se denomina exponente al que pertenece dicho polinomio. Un polinomio irreducible se llama primitivo si todas sus raíces son elementos generadores del grupo multiplicativo del cuerpo [15] .

Todas las raíces de un polinomio primitivo tienen un orden igual al orden del grupo multiplicativo del campo extendido , es decir, [11] . ${\ estilo de visualización \ mathbb {F} _ {Q}}$ $Q-1$

Polinomios circulares

Sea un elemento generador del grupo multiplicativo del campo , y su orden es , es decir . Sean todos los elementos del orden las raíces del polinomio . Entonces tal polinomio se llama circular y la igualdad [16] es verdadera : $\alfa$ $FG(q^{m})$ $n=q^{m}-1$ $\alpha^{q^m-1}=1$ $d$ ${\ estilo de visualización \ psi _ {d} (x), \; n \, \ vdots \, d}$

x^{q^{m}-1}-1=\prod_{d\,\mid \,q^{m}-1}\psi_{d}(x)

Polinomios de Zhegalkin

Entre los polinomios sobre campos finitos, se distinguen especialmente los polinomios de Zhegalkin . Son polinomios de muchas variables sobre el campo [17] . $FG(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}

Usando un polinomio de este tipo, puede especificar cualquier función booleana [18] y de una manera única [17] [19] . $f(x_{1},\;x_{2},\;\ldots,\;x_{N})$

Aplicación

Hay muchos algoritmos que usan polinomios sobre campos y anillos finitos.

Además, los polinomios sobre campos finitos se usan en la codificación moderna de corrección de errores [20] (para describir códigos cíclicos [21] y para decodificar el código Reed-Solomon usando el algoritmo de Euclid [22] ), generadores de números pseudoaleatorios [23] (implementado usando registros de desplazamiento ) [24] , cifrado de transmisión [25] y algoritmos de verificación de integridad de datos.

Véase también

Notas

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

Literatura

Akritas A. Fundamentos de álgebra informática con aplicaciones / per. De inglés. E. V. Pankratieva . — M .: Mir, 1994. — 544 p.
Alferov A. P. , Zubov A. Yu. , Kuzmin A. S. , Cheremushkin A. V. Fundamentos de criptografía : Libro de texto - 3ra ed., Rev. y adicional - M. : Helios ARV , 2005. - 480 p. — ISBN 978-5-85438-137-6
Bleyhut R. E. Teoría y práctica de códigos que controlan errores / ed. K. Sh. Zigangirova , trad. por. De inglés. II Grushko , V. M. Blinovsky - M .: Mir , 1986. - 576 p.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Seguridad de la información : libro de texto - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Sagalovich Yu. L. Introducción a los códigos algebraicos - 3ª ed., revisada. y adicional - M. : IPPI RAN , 2014. - 310 p. — ISBN 978-5-901158-24-1
Yablonsky SV Introducción a las matemáticas discretas : Proc. asignación para universidades - 2ª ed., revisada. y adicional — M .: Nauka , 1986. — 384 p.
Peterson W., Weldon E. Códigos de corrección de errores. - M. : Mir, 1976. - S. 596.