Logaritmo de Zech

Los logaritmos de Zech se utilizan para implementar la suma en cuerpos finitos cuando los elementos se representan como potencias de un generador.${\displaystyle \alpha }$.

Los logaritmos de Zech reciben su nombre de Julius Zech , ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} y también se les llama logaritmos de Jacobi , ^{[ 5 ]} en honor a Carl GJ Jacobi, quien los utilizó para investigaciones de teoría de números . ^{[ 6 ]}

Dado un elemento primitivo${\displaystyle \alpha }$de un campo finito, el logaritmo de Zech relativo a la base${\displaystyle \alpha }$se define mediante la ecuación $${\displaystyle \alpha ^{Z_{\alpha }(n)}=1+\alpha ^{n},}$$ que a menudo se reescribe como $${\displaystyle Z_{\alpha }(n)=\log _{\alpha }(1+\alpha ^{n}).}$$ La elección de la base${\displaystyle \alpha }$Por lo general, se omite de la notación cuando el contexto deja claro que no es necesario.

Para ser más precisos,${\displaystyle Z_{\alpha }}$es una función sobre los enteros módulo el orden multiplicativo de${\displaystyle \alpha }$y toma valores en el mismo conjunto. Para describir cada elemento, es conveniente agregar formalmente un nuevo símbolo.${\displaystyle -\infty }$junto con las definiciones $${\displaystyle \alpha ^{-\infty }=0}$$$${\displaystyle n+(-\infty )=-\infty }$$$${\displaystyle Z_{\alpha }(-\infty )=0}$$$${\displaystyle Z_{\alpha }(e)=-\infty }$$ dónde${\displaystyle e}$es un número entero que satisface${\displaystyle \alpha ^{e}=-1}$, eso es${\displaystyle e=0}$para un campo de característica 2, y${\displaystyle e={\frac {q-1}{2}}}$para un campo de características extrañas con${\displaystyle q}$elementos.

Utilizando el logaritmo de Zech, se puede realizar aritmética de cuerpos finitos en la representación exponencial: $${\displaystyle \alpha ^{m}+\alpha ^{n}=\alpha ^{m}\cdot (1+\alpha ^{nm})=\alpha ^{m}\cdot \alpha ^{Z(nm)}=\alpha ^{m+Z(nm)}}$$$${\displaystyle -\alpha ^{n}=(-1)\cdot \alpha ^{n}=\alpha ^{e}\cdot \alpha ^{n}=\alpha ^{e+n}}$$$${\displaystyle \alpha ^{m}-\alpha ^{n}=\alpha ^{m}+(-\alpha ^{n})=\alpha ^{m+Z(e+nm)}}$$$${\displaystyle \alpha ^{m}\cdot \alpha ^{n}=\alpha ^{m+n}}$$$${\displaystyle \left(\alpha ^{m}\right)^{-1}=\alpha ^{-m}}$$$${\displaystyle \alpha ^{m}/\alpha ^{n}=\alpha ^{m}\cdot \left(\alpha ^{n}\right)^{-1}=\alpha ^{mn}}$$ Estas fórmulas siguen siendo válidas según nuestras convenciones con el símbolo${\displaystyle -\infty }$, con la salvedad de que la resta de${\displaystyle -\infty }$no está definido. En particular, las fórmulas de suma y resta deben tratar${\displaystyle m=-\infty }$como un caso especial.

Esto se puede extender a la aritmética de la línea proyectiva introduciendo otro símbolo.${\displaystyle +\infty }$satisfactorio${\displaystyle \alpha ^{+\infty }=\infty }$y otras normas según corresponda.

Para campos de característica 2, $${\displaystyle Z_{\alpha }(n)=m\iff Z_{\alpha }(m)=n.}$$

Para campos finitos suficientemente pequeños, una tabla de logaritmos de Zech permite una implementación especialmente eficiente de toda la aritmética de campos finitos en términos de un pequeño número de sumas/restas de enteros y búsquedas en tablas.

La utilidad de este método disminuye para campos grandes donde no es posible almacenar la tabla de manera eficiente. Este método también resulta ineficiente al realizar muy pocas operaciones en el campo finito, ya que se dedica más tiempo a calcular la tabla que al cálculo propiamente dicho.

Dejar${\displaystyle \alpha \in \mathrm {GF} (2^{3})}$ser una raíz del polinomio primitivo${\displaystyle x^{3}+x^{2}+1}$. La representación tradicional de los elementos de este campo es como polinomios en${\displaystyle \alpha }$de grado${\displaystyle 2}$o menos.

Aquí hay una tabla de logaritmos de Zech para este campo.

$${\displaystyle Z_{\alpha }(-\infty )=0}$$$${\displaystyle Z_{\alpha}(0)=-\infty}$$$${\displaystyle Z_{\alpha}(1)=5}$$$${\displaystyle Z_{\alpha}(2)=3}$$$${\displaystyle Z_{\alpha}(3)=2}$$$${\displaystyle Z_{\alpha}(4)=6}$$$${\displaystyle Z_{\alpha}(5)=1}$$$${\displaystyle Z_{\alpha}(6)=4}$$

El orden multiplicativo de${\displaystyle \alpha }$es${\displaystyle 7}$, por lo que la representación exponencial funciona con enteros módulo${\displaystyle 7}$.

Desde${\displaystyle \alpha }$es una raíz de${\displaystyle x^{3}+x^{2}+1}$entonces eso significa${\displaystyle \alpha ^{3}+\alpha ^{2}+1=0}$, o si recordamos que dado que todos los coeficientes están en${\displaystyle \mathrm {GF} (2)}$La resta es lo mismo que la suma, obtenemos${\displaystyle \alpha ^{3}=\alpha ^{2}+1}$.

La conversión de representaciones exponenciales a polinómicas viene dada por $${\displaystyle \alpha ^{3}=\alpha ^{2}+1}$$(como se muestra arriba) $${\displaystyle \alpha ^{4}=\alpha ^{3}\alpha =(\alpha ^{2}+1)\alpha =\alpha ^{3}+\alpha =\alpha ^{2}+\alpha +1}$$$${\displaystyle \alpha ^{5}=\alpha ^{4}\alpha =(\alpha ^{2}+\alpha +1)\alpha =\alpha ^{3}+\alpha ^{2}+\alpha =\alpha ^{2}+1+\alpha ^{2}+\alpha =\alpha +1}$$$${\displaystyle \alpha ^{6}=\alpha ^{5}\alpha =(\alpha +1)\alpha =\alpha ^{2}+\alpha }$$

Utilizando logaritmos de Zech para calcular${\displaystyle \alpha ^{6}+\alpha ^{3}}$: $${\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{6+Z(-3)}=\alpha ^{6+Z(4)}=\alpha ^{6+6}=\alpha ^{12}=\alpha ^{5},}$$ o, de manera más eficiente, $${\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{3+Z(3)}=\alpha ^{3+2}=\alpha ^{5},}$$ y verificándolo en la representación polinómica: $${\displaystyle \alpha ^{6}+\alpha ^{3}=(\alpha ^{2}+\alpha )+(\alpha ^{2}+1)=\alpha +1=\alpha ^{5}.}$$

Dado un poder primordial${\displaystyle q=p^{n}}$y un elemento primitivo${\displaystyle \alpha }$de${\displaystyle \mathrm {GF} (q)}$, se puede visualizar el logaritmo de Zech${\displaystyle Z_{\alpha }}$al trazar todos los elementos de${\displaystyle \mathrm {GF} (q)}$en un grafo dirigido,${\displaystyle G_{\alpha }(q)}$:

• Coloca el elemento${\displaystyle 0}$en el centro.
• Ordena los elementos distintos de cero.${\displaystyle \alpha ,\alpha ^{2},\dots ,\alpha ^{q-1}=1}$secuencialmente como nodos igualmente espaciados alrededor de un círculo, con${\displaystyle 1}$en la parte superior.
• Dibuja una arista dirigida.${\displaystyle x\to x+1}$por cada${\displaystyle x}$en${\displaystyle \mathrm {GF} (q)}$.

Los bordes en${\displaystyle G_{\alpha }(q)}$corresponden a las asignaciones en la función logaritmo de Zech: ya que${\displaystyle \alpha ^{Z(n)}=\alpha ^{n}+1}$, un nodo de conexión de arista${\displaystyle \alpha ^{n}}$a${\displaystyle \alpha ^{n}+1}$conecta eficazmente el exponente${\displaystyle n}$al exponente${\displaystyle Z(n)}$.

Aquí está${\displaystyle G_{\alpha }(8)}$, dónde${\displaystyle \alpha }$es una raíz de${\displaystyle x^{3}+x^{2}+1=0}$y los poderes de${\displaystyle \alpha }$se colocan en sentido contrario a las agujas del reloj:

Si uno dibuja un borde${\displaystyle x\to x+c}$en lugar de${\displaystyle x\to x+1}$por cada${\displaystyle x}$en${\displaystyle \mathrm {GF} (q)}$, dónde${\displaystyle c}$Si es cualquier elemento fijo, se obtiene un gráfico.${\displaystyle G_{\alpha }(q;c)}$. El gráfico estándar corresponde a${\displaystyle c=1}$El gráfico${\displaystyle G_{\alpha }(q;0)}$consta de${\displaystyle q}$bucles propios. Para cualquier${\displaystyle c\neq 0}$, el gráfico${\displaystyle G_{\alpha }(q;c)}$parece idéntico a${\displaystyle G_{\alpha }(q)}$, excepto que todos los bordes están rotados por${\displaystyle {\frac {\log _{\alpha }(c)}{q-1}}\times 360^{\circ }}$alrededor del nodo central.

Aquí está${\displaystyle G_{\alpha }(8;\alpha ^{2})}$, que difiere de${\displaystyle G_{\alpha }(8)}$mediante una rotación de${\displaystyle {\frac {2}{7}}\times 360^{\circ }}$:

Cada gráfico${\displaystyle G_{\alpha }(q;c)}$visualiza la permutación${\displaystyle \sigma _{c}(x)=x+c}$. El conjunto de estos${\displaystyle q}$permutaciones${\displaystyle \{\sigma _{c}\mid c\in \mathrm {GF} (q)\}}$forma un grupo abeliano elemental de orden${\displaystyle q}$(isomorfo al grupo aditivo del campo). La simetría rotacional de los gráficos${\displaystyle G_{\alpha }(q;c)}$para${\displaystyle c\neq 0}$Captura elegantemente la indistinguibilidad algebraica de los elementos no nulos en un grupo abeliano elemental.

Si${\displaystyle \alpha }$y${\displaystyle \beta }$son ambos elementos primitivos de${\displaystyle \mathrm {GF} (q)}$, luego los gráficos${\displaystyle G_{\alpha }(q)}$y${\displaystyle G_{\beta }(q)}$son idénticos si y solo si${\displaystyle \alpha }$y${\displaystyle \beta }$son raíces del mismo polinomio primitivo en${\displaystyle \mathrm {GF} (p)[X]}$. Por lo tanto, el número de gráficos distintos${\displaystyle G_{\alpha }(q)}$igual${\displaystyle {\frac {\phi (q-1)}{n}}}$, dónde${\displaystyle \phi }$es la función totiente de Euler . Equivalentemente, existen${\displaystyle {\frac {\phi (q-1)}{n}}}$Tablas de logaritmos de Zech distintas para un tamaño de campo dado.

Si${\displaystyle \alpha }$y${\displaystyle \beta }$son inversos multiplicativos entre sí, entonces${\displaystyle G_{\alpha }(q)}$y${\displaystyle G_{\beta }(q)}$son reflejos el uno del otro.

Cuando${\displaystyle q}$es extraño,${\displaystyle G_{\alpha }(q)}$contiene una arista "diagonal" que conecta el nodo${\displaystyle -1/2}$a${\displaystyle 1/2}$(dónde${\displaystyle 2^{-1}}$denota el inverso multiplicativo de${\displaystyle 1+1}$).

Aquí están los gráficos${\displaystyle G_{\alpha }(q)}$a pesar de${\displaystyle q}$de tal manera que el gráfico permanezca invariante (salvo reflexión) en todos los elementos primitivos.${\displaystyle \alpha }$:

• logaritmo gaussiano
• Logaritmo irlandés , una técnica similar derivada empíricamente por Percy Ludgate.
• Aritmética de cuerpos finitos
• Tabla de logaritmos

• Fletcher, Alan; Miller, Jeffrey Charles Percy ; Rosenhead, Louis (1946) [1943]. Índice de tablas matemáticas (1.ª  ed.). Blackwell Scientific Publications Ltd. , Oxford / McGraw-Hill , Nueva York.
• Conway, John Horton (1968). Churchhouse, Robert F.; Herz, J.-C. (eds.). "Una tabulación de cierta información sobre campos finitos". Computers in Mathematical Research . Ámsterdam: North-Holland Publishing Company : 37–50 . MR 0237467 . 
• Lam, Clement Wing Hong ; McKay, John KS (1973-11-01). "Algoritmo 469: Aritmética sobre un cuerpo finito [ A1 ] " . Communications of the ACM . Collected Algorithms of the ACM (CALGO). 16 (11). Association for Computing Machinery (ACM): 699. doi : 10.1145/355611.362544 . ISSN 0001-0782 . S2CID 62794130 . toms/469.  
• Kühn, Klaus (2008). "CF Gauß und die Logarithmen" (PDF) (en alemán). Alling-Biburg, Alemania. Archivado (PDF) desde el original el 14 de julio de 2018 . Consultado el 14 de julio de 2018 .