Los logaritmos Zech se utilizan para implementar la suma en campos finitos cuando los elementos se representan como potencias de un generador..
Los logaritmos de Zech llevan el nombre de Julius Zech , [1] [2] [3] [4] y también se llaman logaritmos de Jacobi , [5] en honor a Carl GJ Jacobi, quien los usó para investigaciones de teoría de números . [6]
Definición
Dado un elemento primitivo de un campo finito, el logaritmo de Zech relativo a la base está definido por la ecuación
que a menudo se reescribe como
La elección de la base generalmente se elimina de la notación cuando se desprende del contexto.
Ser más preciso, es una función en 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
dónde es un entero satisfactorio , es decir para un campo de característica 2, y para un campo de característica extraña con elementos.
Usando el logaritmo de Zech, la aritmética de campo finito se puede hacer en la representación exponencial:
Estas fórmulas siguen siendo verdaderas con nuestras convenciones con el símbolo , con la salvedad de que la resta de es indefinido. En particular, las fórmulas de suma y resta deben tratar como un caso especial.
Esto se puede extender a la aritmética de la línea proyectiva introduciendo otro símbolo satisfactorio y otras reglas según corresponda.
Para campos de la característica dos,
- .
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 de tablas.
La utilidad de este método disminuye para campos grandes donde no se puede almacenar la tabla de manera eficiente. Este método también es ineficaz cuando se realizan muy pocas operaciones en el campo finito, porque se pasa más tiempo calculando la tabla que en el cálculo real.
Ejemplos de
Sea α ∈ GF (2 3 ) una raíz del polinomio primitivo x 3 + x 2 + 1 . La representación tradicional de elementos de este campo es como polinomios en α de grado 2 o menos.
Una tabla de logaritmos de Zech para este campo es 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.
Dado que α es una raíz de x 3 + x 2 + 1, entonces eso significa α 3 + α 2 + 1 = 0 , o si recordamos que dado que todos los coeficientes están en GF (2), la resta es lo mismo que la suma, obtenemos α 3 = α 2 + 1 .
La conversión de representaciones exponenciales a polinomiales viene dada por
- (como se muestra arriba)
Usando logaritmos de Zech para calcular α 6 + α 3 :
- ,
o, de manera más eficiente,
- ,
y verificándolo en la representación polinomial:
- .
Ver 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
- ↑ Zech, Julius August Christoph (1849). Tafeln der Additions- und Subtractions-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 ; Zech, Julius August Christoph (eds.). Sammlung Mathischer Tafeln (en alemán) (Ed. Completamente reelaborado). Leipzig: Weidmann'sche Buchhandlung . Bibcode : 1849smt..book ..... V . Archivado desde el original el 14 de julio de 2018 . Consultado el 14 de julio de 2018 .
- ^ Zech, Julius August Christoph (1863) [1849]. Tafeln der Additions- und Subtractions-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 .
- ^ Zech, Julius August Christoph (1892) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (en alemán) (Reimpresión especial (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 .
- ^ Zech, Julius August Christoph (1910) [1849]. Tafeln der Additions- und Subtractions-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 .
- ^ Lidl, Rudolf; Niederreiter, Harald (1997). Campos finitos (2ª ed.). Prensa de la Universidad de Cambridge . ISBN 978-0-521-39231-0.
- ^ 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.)
Otras lecturas
- 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 alguna información relativa a campos finitos". Computadoras en la investigación matemática . Amsterdam: North-Holland Publishing Company : 37–50. Señor 0237467 .
- Lam, Clement Wing Hong ; McKay, John KS (1 de noviembre de 1973). "Algoritmo 469: Aritmética sobre un campo finito [A1]". Comunicaciones de la ACM . Algoritmos recopilados del ACM (CALGO). Asociación de Maquinaria de Computación (ACM). 16 (11): 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 .