logarytm Zacha

Logarytmy Zacha $,$ używane do implementacji dodawania w polach skończonych gdy elementy są reprezentowane jako potęgi generatora .

Logarytmy Zecha zostały nazwane na cześć Juliusa Zecha i są również nazywane logarytmami Jacobiego , na cześć Carla GJ Jacobiego , który użył ich do badań teorii liczb .

Definicja

Biorąc pod uwagę $skończonego$ element pola , logarytm Zacha względem podstawy jest określony równaniem ${\ displaystyle \ alpha}$

${\ Displaystyle \ alfa ^ {Z _ {\ alfa} (n)} = 1 + \ alfa ^ {n},}$

co jest często przepisywane jako

${\ Displaystyle Z _ {\ alfa} (n) = \ log _ {\ alfa} (1+ \ alfa ^ {n}).}$

Wybór podstawy $zapisu,$ gdy wynika to z kontekstu.

$jest$ dokładniej, funkcją na liczbach całkowitych modulo rzędu multiplikatywnego i $przyjmuje$ wartości z tego samego Aby opisać każdy element, wygodnie jest formalnie dodać nowy symbol wraz z definicjami ${\ displaystyle - \ infty}$

${\ Displaystyle \ alfa ^ {- \ infty} = 0}$

${\ Displaystyle n + (- \ infty) = - \ infty}$

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

${\ Displaystyle Z _ {\ alfa} (e) = - \ infty}$

gdzie $mi$ liczbą całkowitą spełniającą $czyli$ dla pola o $-1} {2}}}$ i $e$$Displaystyle e = {\ Frac {$ dla pola o dziwnej charakterystyce z elementami.

Używając logarytmu Zacha, arytmetykę pola skończonego można przeprowadzić w reprezentacji wykładniczej:

${\ Displaystyle \ alfa ^ {m} + \ alfa ^{n}=\alpha ^{m}\cdot (1+\alpha ^{nm})=\alpha ^{m}\cdot \alpha ^{Z(nm)}=\alpha ^{m+Z( nm)}}$

${\ Displaystyle - \ alfa ^ {n} = (-1) \ cdot \ alfa ^ {n} = \ alfa ^ {e} \ cdot \ alfa ^{n}=\alpha ^{e+n}}$

${\ Displaystyle \ alfa ^ {m} - \ alfa ^ {n} = \ alfa ^ {m} + (- \ alfa ^ {n}) = \ alfa ^ {m + Z (e + nm)}}$

${\ Displaystyle \ alfa ^ {m} \ cdot \ alfa ^ {n} = \ alfa ^ {m + n}} ($

$\ Displaystyle \ lewo (\alpha ^{m}\right)^{-1}=\alpha ^{-m}}$

${\ Displaystyle \ alfa ^ {m}/\ alfa ^ {n} = \ alfa ^ {m} \ cdot \ lewo (\ alfa ^ {n} \ prawo) ^ {- 1} = \ alfa ^{mln}}$

$odejmowanie$ konwencjach z symbolem , z zastrzeżeniem, $jest$$przypadek$ traktować jako

$to$ rozszerzyć na arytmetykę linii rzutowej $,$ inny spełniający i

Dla pól charakterystycznych dwa,

${\ Displaystyle Z _ {\ alfa} (n) = m \ if Z _ {\ alfa} (m) = n}$ .

Używa

W przypadku wystarczająco małych pól skończonych tablica logarytmów Zacha pozwala na szczególnie wydajną implementację całej arytmetyki pól skończonych pod względem niewielkiej liczby dodawania/odejmowania liczb całkowitych i przeglądania tabeli.

Użyteczność tej metody maleje w przypadku dużych pól, gdzie nie można efektywnie przechowywać tabeli. Ta metoda jest również nieefektywna, gdy wykonuje się bardzo niewiele operacji na polu skończonym, ponieważ spędza się więcej czasu na obliczaniu tabeli niż na rzeczywistych obliczeniach.

Przykłady

Niech α ∈ GF(2 ³ ) będzie pierwiastkiem pierwotnego wielomianu x ³ + x ² + 1 . Tradycyjna reprezentacja elementów tego pola to wielomiany w α stopnia 2 lub mniejszego.

Tabela logarytmów Zacha dla tego pola to Z (−∞) = 0 , Z (0) = −∞ , Z (1) = 5 , Z (2) = 3 , Z (3) = 2 , Z (4) = 6 , Z (5) = 1 i Z (6) = 4 . Rząd multiplikatywny α wynosi 7, więc reprezentacja wykładnicza działa z liczbami całkowitymi modulo 7.

Ponieważ α jest pierwiastkiem z x ³ + x ² + 1 , oznacza to, że α ³ + α ² + 1 = 0 , lub jeśli przypomnimy sobie, że ponieważ wszystkie współczynniki są w GF(2), odejmowanie jest tym samym co dodawanie, otrzymujemy α ³ = α ² + 1 .

Konwersja z reprezentacji wykładniczych na wielomianowe jest dana przez

${\ Displaystyle \ alfa ^ {3} = \ alfa ^ {2} + 1}$ (jak pokazano powyżej)

${\ Displaystyle \ alfa ^ {4} = \ alfa ^ {3} \ alfa = (\ alfa ^ {2} + 1) \ alfa = \ alfa ^ {3} + \ alfa = \ alfa ^{2}+\alfa +1}$

${\ Displaystyle \ alfa ^ {5} = \ alfa ^ {4} \ alpha =(\alpha ^{2}+\alpha +1)\alpha =\alpha ^{3}+\alpha ^{2}+\alpha =\alpha ^{2}+1+\alpha ^{2} +\alfa =\alfa +1}$

${\ Displaystyle \ alfa ^ {6} = \ alfa ^ {5} \ alfa = (\ alfa + 1) \ alfa = \ alfa ^ {2} + \ alfa}$

Używając logarytmów Zacha do obliczenia α ⁶ + α ³ :

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

lub, wydajniej,

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

i weryfikując to w reprezentacji wielomianowej:

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

Zobacz też

• Logarytm Gaussa
• Logarytm irlandzki , podobna technika wyprowadzona empirycznie przez Percy'ego Ludgate'a
• Arytmetyka pola skończonego
• Tabela logarytmów

Dalsza lektura

• Fletcher, Alan; Miller, Jeffrey Charles Percy ; Rosenhead, Louis (1946) [1943]. Indeks tablic matematycznych (1 wyd.). Blackwell Scientific Publications Ltd. , Oxford / McGraw-Hill , Nowy Jork.
•   Conway, John Horton (1968). Churchhouse, Robert F.; Herz, J.-C. (red.). „Tabela niektórych informacji dotyczących pól skończonych”. Komputery w badaniach matematycznych . Amsterdam: North-Holland Publishing Company : 37–50. MR 0237467 .
•    Lam, Clement Wing Hong ; McKay, John KS (1973-11-01). „Algorytm 469: Arytmetyka na polu skończonym [A1]” . Komunikaty ACM . Zebrane algorytmy ACM (CALGO). Stowarzyszenie Maszyn Komputerowych (ACM). 16 (11): 699. doi : 10.1145/355611.362544 . ISSN 0001-0782 . S2CID 62794130 . tomy/469. [1] [2] [3]
• Kühn, Klaus (2008). „CF Gauß und die Logarithmen” (PDF) (w języku niemieckim). Alling-Biburg, Niemcy. Zarchiwizowane (PDF) od oryginału w dniu 14.07.2018 r . Źródło 2018-07-14 .