Un (base-$g$) del logaritmo discreto de un campo finito $\Bbb{F}_q$, es una función
$$
\log_g:\Bbb{F}_q^*\a\Bbb{Z}_{q-1}
$$
se define a través de la equivalencia $g^j=x\Leftrightarrow \log_g(x)=j$. Para que esto sea bien definido es imperativo que $g$ es un elemento primitivo, es decir, un generador de $\Bbb{F}_q^*$, y que el dominio de la $\log_g$ es la
residuo anillo de la clase de los enteros modulo $q-1$$g^{q-1}=g^0=1$.
Se sigue inmediatamente que el logaritmo discreto satisface las conocidas reglas de
$$
\begin{aligned}
\log_g(x\cdot y)&=\log_g(x)+\log_g(y),\\
\log_g(x^n)&=n\cdot\log_g(x)
\end{aligned}
$$
para todos los elementos de la $x,y\in \Bbb{F}_q^*$ y todos los números enteros $n$. La aritmética
en la r.h.s. es que de el anillo de $\Bbb{Z}_{q-1}$.
Es sabido que cuando $q=8$, un cero $\alpha$ $x^3+x+1$ genera $\Bbb{F}_8^*$. Esto es demostrado por el siguiente cálculo, en caso de que en repetidas ocasiones
utilice el hecho de que estamos trabajando en el carácter de los dos, y que tenemos la
relación $\alpha^3=\alpha+1$.
$$
\eqalign{
\alpha^0&=&&=1,\\
\alpha^1&=&&=\alpha,\\
\alpha^2&=&&=\alpha^2,\\
\alpha^3&=&&=1+\alpha,\\
\alpha^4&=&\alpha\cdot\alpha^3=\alpha(1+\alpha)&=\alpha+\alpha^2,\\
\alpha^5&=&\alpha\cdot\alpha^4=\alpha(\alpha+\alpha^2)=\alpha^2+\alpha^3=\alpha^2+(1+\alpha)&=1+\alpha+\alpha^2,\\
\alpha^6&=&\alpha\cdot\alpha^5=\alpha(1+\alpha+\alpha^2)=\alpha+\alpha^2+\alpha^3=
\alpha+\alpha^2+(1+\alpha) y=1+\alpha^2,\\
\alpha^7&=&\alpha\cdot\alpha^6=\alpha(1+\alpha^2)=\alpha+\alpha^3=\alpha+(1+\alpha) y=1.
}$$
Vemos a partir de los resultados finales en la última columna que todos los no-cero
polinomios cuadráticos evaluados en $\alpha$ aparecen. Esta es otra confirmación de que el hecho de que $\alpha$ es un elemento primitivo.
El logaritmo discreto es usado para reemplazar el engorroso multiplicación (y de sensibilización
a una potencia entera) en el campo, con más familiar aritmética de enteros. Exactamente igual que el anterior-temporizadores utilizados logaritmo de tablas para compensar el error propensas a la multiplicación con la más fácil, además.
Por ejemplo
$$
(1+\alpha)(1+\alpha+\alpha^2)=\alpha^3\cdot\alpha^5=\alpha^8=\alpha^7\cdot\alpha=\alpha.
$$
Tenga en cuenta que tanto la base-$\alpha$ logaritmos discretos y su inversa la cartografía necesaria. Generar una tabla como parte de la inicialización del programa, siempre que puedo llevar a cabo extensas asistido por ordenador cálculos que implican un campo finito. La tabla anterior da el logaritmo discreto cuando se leen de derecha a izquierda, y el inverso de asignación (que en realidad producido por encima) cuando se leen de izquierda a derecha.
De igual manera, con $q=16$$\gamma$, un cero de $x^4+x+1$. Esta vez la apariencia de la tabla
$$
\begin{aligned}
\gamma^0&=&1\\
\gamma^1&=&\gamma\\
\gamma^2&=&\gamma^2\\
\gamma^3&=&\gamma^3\\
\gamma^4&=&\gamma+1\\
\gamma^5&=\gamma(\gamma+1)=&\gamma^2+\gamma\\
\gamma^6&=\gamma(\gamma^2+\gamma)=&\gamma^3+\gamma^2\\
\gamma^7&=\gamma^4+\gamma^3=&\gamma^3+\gamma+1\\
\gamma^8&=(\gamma^4)^2=&\gamma^2+1\\
\gamma^9&=\gamma(\gamma^2+1)=&\gamma^3+\gamma\\
\gamma^{10}&=\gamma^4+\gamma^2=&\gamma^2+\gamma+1\\
\gamma^{11}&=&\gamma^3+\gamma^2+\gamma\\
\gamma^{12}&=\gamma^4+\gamma^3+\gamma^2=&\gamma^3+\gamma^2+\gamma+1\\
\gamma^{13}&=\gamma^4+\gamma^3+\gamma^2+\gamma=&\gamma^3+\gamma^2+1\\
\gamma^{14}&=\gamma^4+\gamma^3+\gamma=&\gamma^3+1\\
(\gamma^{15}&=\gamma^4+\gamma=&1)
\end{aligned}
$$
Así, por ejemplo,
$$
(\gamma^3+1)(\gamma^2+1)=\gamma^{14}\cdot\gamma^8=\gamma^{22}=\gamma^7=\gamma^3+\gamma+1.
$$
Como otro ejemplo del uso de esta tabla, quiero discutir el problema de la factorización de $x^4+x+1$$\Bbb{F}_4$. Para ello primero tenemos que identificar a una copia de $\Bbb{F}_4$ como un subcampo de la $\Bbb{F}_{16}$. Acabamos de ver que $\gamma$ es del orden de los quince. Por lo tanto, $\gamma^5=\gamma^2+\gamma$ $\gamma^{10}=\gamma^2+\gamma+1$ son de tercera raíces de la unidad. Entonces es trivial comprobar que tenemos un homomorphism de los campos de $\sigma:\Bbb{F}_4\to\Bbb{F}_{16}$$\sigma(\beta)=\gamma^5$. Tenga en cuenta que la composición de este (desde cualquiera de los extremos) por el Frobenius automorphism da una alternativa de incrustación $\beta\mapsto \gamma^{10}$.
Básicos de la teoría de Galois nos dice que
$$
x^4+x+1=(x-\gamma)(x-\gamma^2)(x-\gamma^4)(x-\gamma^8)
$$
como obtenemos las otras raíces por aplicar repetidamente el Frobenius automorphism $F:x\mapsto x^2$. Aquí podemos ver que el factor de
$$
(x-\gamma)(x-\gamma^4)=x^2+x(\gamma+\gamma^4)+\gamma^5=x^2+x+\gamma^5
$$
es estable bajo la automorphism $F^2$, y por lo tanto (como también vemos directamente!) tiene su
los coeficientes en el subcampo $\sigma(\Bbb{F}_4)$. Lo mismo vale para el resto de factor de
$$
(x-\gamma^2)(x-\gamma^8)=x^2+x(\gamma^2+\gamma^8)+\gamma^{10}=x^2+x+\gamma^{10}.
$$
Tirando hacia atrás el efecto de la $\sigma$ obtenemos el deseado de la factorización de
$$
x^4+x+1=(x^2+x+\beta)(x^2+x+\beta+1)
$$
en $\Bbb{F}_4[x]$.
