Logaritmo de Zech

Los logaritmos de Zech se utilizan para implementar la suma en campos 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 de un campo finito, el logaritmo de Zech relativo a la base se define mediante la ecuación que a menudo se reescribe como La elección de la base generalmente se omite de la notación cuando es clara por el contexto. ${\displaystyle \alpha }$${\displaystyle \alpha }$$${\displaystyle \alpha ^{Z_{\alpha }(n)}=1+\alpha ^{n},}$$$${\displaystyle Z_{\alpha }(n)=\log _{\alpha }(1+\alpha ^{n}).}$$${\displaystyle \alpha }$

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

Utilizando el logaritmo de Zech, la aritmética de cuerpos finitos se puede realizar en la representación exponencial: Estas fórmulas siguen siendo válidas con nuestras convenciones con el símbolo , con la salvedad de que la resta de no está definida. En particular, las fórmulas de suma y resta deben tratar como un caso especial. $${\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}}$$${\displaystyle -\infty }$${\displaystyle -\infty }$${\displaystyle m=-\infty }$

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

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.

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

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 es , por lo que la representación exponencial funciona con enteros módulo . ${\displaystyle \alpha }$${\displaystyle 7}$${\displaystyle 7}$

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

La conversión de representaciones exponenciales a polinómicas viene dada por (como se muestra arriba) $${\displaystyle \alpha ^{3}=\alpha ^{2}+1}$$$${\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 : o, de forma más eficiente, y verificándolo en la representación polinómica: ${\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},}$$$${\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{3+Z(3)}=\alpha ^{3+2}=\alpha ^{5},}$$$${\displaystyle \alpha ^{6}+\alpha ^{3}=(\alpha ^{2}+\alpha )+(\alpha ^{2}+1)=\alpha +1=\alpha ^{5}.}$$

Dado un exponente primo y un elemento primitivo de , se puede visualizar el logaritmo de Zech representando gráficamente todos los elementos de en un grafo dirigido, : ${\displaystyle q=p^{n}}$${\displaystyle \alpha }$${\displaystyle \mathrm {GF} (q)}$${\displaystyle Z_{\alpha }}$${\displaystyle \mathrm {GF} (q)}$${\displaystyle G_{\alpha }(q)}$

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

Las aristas corresponden a las asignaciones en la función logaritmo de Zech: dado que , una arista que conecta el nodo con conecta efectivamente el exponente con el exponente . ${\displaystyle G_{\alpha }(q)}$${\displaystyle \alpha ^{Z(n)}=\alpha ^{n}+1}$${\displaystyle \alpha ^{n}}$${\displaystyle \alpha ^{n}+1}$${\displaystyle n}$${\displaystyle Z(n)}$

Aquí está , donde es una raíz de , y las potencias de se colocan en orden antihorario: ${\displaystyle G_{\alpha }(8)}$${\displaystyle \alpha }$${\displaystyle x^{3}+x^{2}+1=0}$${\displaystyle \alpha }$

Si se dibuja una arista en lugar de para cada en , donde es cualquier elemento fijo, se obtiene un grafo . El grafo estándar corresponde a . El grafo consta de bucles. Para cualquier , el grafo parece idéntico a , excepto que todas las aristas están rotadas en alrededor del nodo central. ${\displaystyle x\to x+c}$${\displaystyle x\to x+1}$${\displaystyle x}$${\displaystyle \mathrm {GF} (q)}$${\displaystyle c}$${\displaystyle G_{\alpha }(q;c)}$${\displaystyle c=1}$${\displaystyle G_{\alpha }(q;0)}$${\displaystyle q}$${\displaystyle c\neq 0}$${\displaystyle G_{\alpha }(q;c)}$${\displaystyle G_{\alpha }(q)}$${\displaystyle {\frac {\log _{\alpha }(c)}{q-1}}\times 360^{\circ }}$

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

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

Si y son elementos primitivos de , entonces las gráficas y son idénticas si y solo si y son raíces del mismo polinomio primitivo en . Por lo tanto, el número de gráficas distintas es igual a , donde es la función totiente de Euler . De forma equivalente, existen tablas de logaritmos de Zech distintas para un tamaño de campo dado. ${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \mathrm {GF} (q)}$${\displaystyle G_{\alpha }(q)}$${\displaystyle G_{\beta }(q)}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \mathrm {GF} (p)[X]}$${\displaystyle G_{\alpha }(q)}$${\displaystyle {\frac {\phi (q-1)}{n}}}$${\displaystyle \phi }$${\displaystyle {\frac {\phi (q-1)}{n}}}$

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

Cuando es impar, contiene una arista "diagonal" que conecta el nodo con (donde denota el inverso multiplicativo de ). ${\displaystyle q}$${\displaystyle G_{\alpha }(q)}$${\displaystyle -1/2}$${\displaystyle 1/2}$${\displaystyle 2^{-1}}$${\displaystyle 1+1}$

Aquí están los gráficos para todos los tales que el gráfico permanece invariante (salvo reflexión) en todos los elementos primitivos : ${\displaystyle G_{\alpha }(q)}$${\displaystyle q}$${\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.[1] [2] [3]
• 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 .