Logaritmo de Zech

Herramienta para una aritmética rápida de campos finitos

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

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

Definición

Dado un elemento primitivo de un cuerpo finito, el logaritmo Zech relativo a la base se define por la ecuación ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

${\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 generalmente se omite de la notación cuando queda claro a partir del contexto. ${\displaystyle \alpha }$

Para ser más precisos, es una función de los números enteros módulo el orden multiplicativo de , y toma valores del mismo conjunto. Para describir cada elemento, es conveniente agregar formalmente un nuevo símbolo , junto con las definiciones. ${\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 }$

donde es un entero que satisface , es decir para un campo de característica 2, y para un campo de característica impar con elementos. ${\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 campos finitos se puede realizar en la representación exponencial:

${\displaystyle \alpha ^{m}+\alpha ^{n}=\alpha ^{m}\cdot (1+\alpha ^{n-m})=\alpha ^{m}\cdot \alpha ^{Z(n-m)}=\alpha ^{m+Z(n-m)}}$

${\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+n-m)}}$

${\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 ^{m-n}}$

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 tratarse como un caso especial. ${\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 otras reglas según sea apropiado. ${\displaystyle +\infty }$ ${\displaystyle \alpha ^{+\infty }=\infty }$

Para los campos de característica 2,

${\displaystyle Z_{\alpha }(n)=m\iff Z_{\alpha }(m)=n}$.

Usos

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 la tabla.

La utilidad de este método disminuye en el caso de campos grandes en los que no se puede almacenar la tabla de manera eficiente. Este método también es ineficiente cuando se realizan muy pocas operaciones en el campo finito, porque se dedica más tiempo a calcular la tabla que al cálculo real.

Ejemplos

Sea α ∈ GF(2 ³ ) una raíz del polinomio primitivo x ³ + x ² + 1 . La representación tradicional de los elementos de este cuerpo es como polinomios en α de grado 2 o menor.

Una tabla de logaritmos de Zech para este campo son Z (−∞) = 0 , Z (0) = −∞ , Z (1) = 5 , Z (2) = 3 , Z (3) = 2 , Z (4) = 6 , Z (5) = 1 y Z (6) = 4. El orden multiplicativo de α es 7, por lo que la representación exponencial funciona con números enteros módulo 7.

Como α es una raíz de x ³ + x ² + 1 entonces eso significa α ³ + α ² + 1 = 0 , o si recordamos que como todos los coeficientes están en GF(2), la resta es lo mismo que la suma, obtenemos α ³ = α ² + 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 }$

Usando logaritmos de Zech para calcular α ⁶ + α ³ :

${\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{6+Z(-3)}=\alpha ^{6+Z(4)}=\alpha ^{6+6}=\alpha ^{12}=\alpha ^{5},}$

o, más eficientemente,

${\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{3+Z(3)}=\alpha ^{3+2}=\alpha ^{5},}$

y verificarlo en la representación polinomial:

${\displaystyle \alpha ^{6}+\alpha ^{3}=(\alpha ^{2}+\alpha )+(\alpha ^{2}+1)=\alpha +1=\alpha ^{5}.}$

Véase también

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

Referencias

1. Zech, Julius August Christoph (1849). Tafeln der Additions- und Rests-Logarithmen für sieben Stellen (en alemán) (reimpreso especialmente (de la colección Vega – Hülße) 1ª ed.). Leipzig: Weidmann'sche Buchhandlung . Archivado desde el original el 14 de julio de 2018 . Consultado el 14 de julio de 2018 .También forma parte de: Freiherr von Vega, Georg (1849). Hülße, Julius Ambrosius [en alemán] ; Zech, Julius August Christoph (eds.). Sammlung mathematischer Tafeln (en alemán) (edición completamente reelaborada). Leipzig: Weidmann'sche Buchhandlung . Bibcode : 1849smt..libro.....V. Archivado desde el original el 14 de julio de 2018 . Consultado el 14 de julio de 2018 .
2. Zech, Julius August Christoph (1863) [1849]. Tafeln der Additions- und Rests-Logarithmen für sieben Stellen (en alemán) (reimpreso especialmente (de la colección Vega – Hülße) 2ª ed.). Berlín: Weidmann'sche Buchhandlung . Archivado desde el original el 14 de julio de 2018 . Consultado el 13 de julio de 2018 .
3. Zech, Julius August Christoph (1892) [1849]. Tafeln der Additions- und Rests-Logarithmen für sieben Stellen (en alemán) (reimpreso especialmente (de la colección Vega – Hülße) 3ª ed.). Berlín: Weidmann'sche Buchhandlung . Archivado desde el original el 14 de julio de 2018 . Consultado el 13 de julio de 2018 .
4. Zech, Julius August Christoph (1910) [1849]. Tafeln der Additions- und Rests-Logarithmen für sieben Stellen (en alemán) (reimpreso especialmente (de la colección Vega – Hülße) 4ª ed.). Berlín: Weidmann'sche Buchhandlung . Archivado desde el original el 14 de julio de 2018 . Consultado el 13 de julio de 2018 .
5. Lidl, Rudolf; Niederreiter, Harald (1997). Campos finitos (2ª ed.). Prensa de la Universidad de Cambridge . ISBN 978-0-521-39231-0.
6. Jacoby, Carl Gustav Jacob (1846). "Über die Kreistheilung und ihre Anwendung auf die Zahlentheorie". Journal für die reine und angewandte Mathematik (en alemán). 1846 (30): 166–182. doi :10.1515/crll.1846.30.166. ISSN  0075-4102. S2CID  120615565.(NB. También forma parte de "Gesammelte Werke", volumen 6, páginas 254–274.)

Lectura adicional

• Fletcher, Alan; Miller, Jeffrey Charles Percy ; Rosenhead, Louis (1946) [1943]. Un í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 concerniente a campos finitos". Computadoras en la investigación matemática . Á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 campo finito [A1]". Comunicaciones de la ACM . Algoritmos recopilados de la 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 .