Zechsův logaritmus - Zechs logarithm - Wikipedia

Zech logaritmy se používají k implementaci přidání do konečná pole když jsou prvky reprezentovány jako síly generátoru ${ displaystyle alpha}$.

Zech logaritmy jsou pojmenovány po Julius Zech,^[1][2][3][4] a jsou také voláni Jacobiho logaritmy,^[5] po Carl G. J. Jacobi kdo je použil teoretický počet vyšetřování.^[6]

Definice

Vzhledem k primitivní prvek ${ displaystyle alpha}$ konečného pole, Zechův logaritmus vzhledem k základně ${ displaystyle alpha}$ je definována rovnicí

${ displaystyle Z _ { alpha} (n) = log _ { alpha} (1+ alpha ^ {n}),}$

nebo ekvivalentně

${ displaystyle alpha ^ {Z _ { alpha} (n)} = 1+ alpha ^ {n}.}$

Volba základny ${ displaystyle alpha}$ je obvykle vynechán z notace, když je to jasné z kontextu.

Být přesnější, ${ displaystyle Z _ { alpha}}$ je funkce na celá čísla modulo multiplikativní pořadí ${ displaystyle alpha}$a přebírá hodnoty ve stejné sadě. Aby bylo možné popsat každý prvek, je vhodné formálně přidat nový symbol ${ displaystyle - infty}$spolu s definicemi

${ displaystyle alpha ^ {- infty} = 0}$

${ displaystyle n + (- infty) = - infty}$

${ displaystyle Z _ { alpha} (- infty) = 0}$

${ displaystyle Z _ { alpha} (e) = - infty}$

kde ${ displaystyle e}$ je celé číslo uspokojující ${ displaystyle alpha ^ {e} = - 1}$, to je ${ displaystyle e = 0}$ pro pole charakteristiky 2 a ${ displaystyle e = { frac {q-1} {2}}}$ pro pole liché charakteristiky s ${ displaystyle q}$ elementy.

Pomocí Zechova logaritmu lze provést aritmetiku konečných polí v exponenciálním vyjádření:

${ 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 + 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}}$

Tyto vzorce zůstávají věrné našim konvencím se symbolem ${ displaystyle - infty}$s výhradou, že odečtení ${ displaystyle - infty}$ není definováno. Zejména je třeba ošetřit vzorce pro sčítání a odčítání ${ displaystyle m = - infty}$ jako zvláštní případ.

To lze rozšířit na aritmetiku projektivní linie zavedením dalšího symbolu ${ displaystyle + infty}$ uspokojující ${ displaystyle alpha ^ {+ infty} = infty}$ a případně další pravidla.

Všimněte si, že pro pole charakteristiky dva,

${ displaystyle Z _ { alpha} (n) = m}$ ⇔ ${ displaystyle Z _ { alpha} (m) = n}$.

Použití

Pro dostatečně malá konečná pole umožňuje tabulka Zechových logaritmů obzvláště efektivní implementaci aritmetiky všech konečných polí, pokud jde o malý počet sčítání / odčítání celých čísel a vyhledávání tabulek.

Užitečnost této metody klesá u velkých polí, kde nelze efektivně uložit tabulku. Tato metoda je také neefektivní, když děláte jen velmi málo operací v konečném poli, protože člověk stráví více času výpočtem tabulky než jeden ve skutečném výpočtu.

Příklady

Nechat α ∈ GF (2³) být kořenem primitivní polynom X³ + X² + 1. Tradiční reprezentace prvků tohoto pole je jako polynomy v α stupně 2 nebo méně.

Tabulka Zechových logaritmů pro toto pole je Z(−∞) = 0, Z(0) = −∞, Z(1) = 5, Z(2) = 3, Z(3) = 2, Z(4) = 6, Z(5) = 1, a Z(6) = 4. Multiplikativní pořadí α je 7, takže exponenciální reprezentace pracuje s celými čísly modulo 7.

Od té doby α je kořenem X³ + X² + 1 pak to znamená α³ + α² + 1 = 0, nebo pokud si vzpomeneme, že protože všechny koeficienty jsou v GF (2), odčítání je stejné jako sčítání, získáme α³ = α² + 1.

Převod z exponenciálních na polynomické reprezentace je dán vztahem

${ displaystyle alpha ^ {3} = alpha ^ {2} +1}$ (jak je uvedeno výše)

${ displaystyle alpha ^ {4} = alpha ^ {3} alpha = ( alpha ^ {2} +1) alpha = alpha ^ {3} + alpha = alpha ^ {2} + alfa +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}$

Použití Zech logaritmů k výpočtu α⁶ + α³:

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

nebo, efektivněji,

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

a jeho ověření v polynomické reprezentaci:

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

Viz také

• Gaussův logaritmus
• Irský logaritmus, podobná technika odvozená empiricky Percy Ludgate
• Aritmetika konečného pole
• Logaritmická tabulka

Reference

Další čtení

• Fletcher, Alan; Miller, Jeffrey Charles Percy; Rosenhead, Louis (1946) [1943]. Rejstřík matematických tabulek (1. vyd.). Blackwell Scientific Publications Ltd., Oxford / McGraw-Hill, New York.
• Conway, John Horton (1968). Churchhouse, Robert F .; Herz, J.-C. (eds.). Msgstr "Tabulka některých informací týkajících se konečných polí". Počítače v matematickém výzkumu. Amsterdam: Nakladatelská společnost North-Holland: 37–50. PAN  0237467.
• Lam, Clement Wing Hong; McKay, John K. S. (1973-11-01). "Algoritmus 469: Aritmetika přes konečné pole [A1]". Komunikace ACM. Shromážděné algoritmy ACM (CALGO). Sdružení pro výpočetní techniku (ACM). 16 (11): 699. doi:10.1145/355611.362544. ISSN  0001-0782. S2CID  62794130. toms / 469. [1] [2] [3]
• Kühn, Klaus (2008). „C. F. Gauß und die Logarithmen“ (PDF) (v němčině). Alling-Biburg, Německo. Archivováno (PDF) od originálu na 2018-07-14. Citováno 2018-07-14.