Zech logaritmusa - Zech's logarithm

A Zech logaritmusokat arra használjuk, hogy véges mezőkben megvalósítsuk az összeadást, amikor az elemeket egy generátor teljesítményeként ábrázoljuk . ${\ displaystyle \ alpha}$

A zech logaritmusokat Julius Zechről nevezik el , és Jacobi logaritmusoknak is nevezik , Carl GJ Jacobi után, aki számelméleti vizsgálatokhoz használta őket .

Meghatározás

A véges mező primitív elemét figyelembe véve a Zech logaritmust az alaphoz képest az egyenlet határozza meg ${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$

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

amelyet gyakran úgy írnak át

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

A bázis megválasztása általában akkor kerül ki a jelölésből, ha az egyértelmű a kontextusból. ${\ displaystyle \ alpha}$

Pontosabban : a modulo egész számok függvénye a szorzási sorrend , és ugyanabban a halmazban vesz fel értékeket. Minden elem leírása érdekében célszerű formálisan új szimbólumot adni a definíciókkal együtt ${\ 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}$

ahol van egy egész szám kielégítő , azaz egy mező a jellemző 2, és egy mező páratlan karakterisztika elemekkel. ${\ displaystyle e}$${\ displaystyle \ alpha ^ {e} = - 1}$${\ displaystyle e = 0}$${\ displaystyle e = {\ frac {q-1} {2}}}$${\ displaystyle q}$

A Zech logaritmus segítségével a véges mező számtana elvégezhető az exponenciális ábrázolásban:

${\ displaystyle \ alpha ^ {m} + \ alpha ^ {n} = \ alpha ^ {m} \ cdot (1+ \ alpha ^ {nm}) = \ alpha ^ {m} \ cdot \ alpha ^ {Z ( nm)} = \ alfa ^ {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}}$

Ezek a képletek igazak maradnak a szimbólumú konvencióinknál , azzal a figyelmeztetéssel, amelynek kivonása nincs meghatározva. Különösen az összeadási és kivonási képleteket kell speciális esetként kezelni . ${\ displaystyle - \ infty}$${\ displaystyle - \ infty}$${\ displaystyle m = - \ infty}$

Ez kiterjeszthető a vetítő vonal aritmetikájára egy másik megfelelő szimbólum és adott esetben más szabályok bevezetésével . ${\ displaystyle + \ infty}$${\ displaystyle \ alpha ^ {+ \ infty} = \ infty}$

A kettőre jellemző mezők esetében

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

Használ

Kellően kicsi véges mezők esetén a Zech logaritmusok táblázata lehetővé teszi az összes véges mező aritmetika különösen hatékony végrehajtását kis számú egész szám összeadás / kivonás és tábla keresés szempontjából.

E módszer hasznossága csökken azoknál a nagy mezőknél, ahol nem lehet hatékonyan tárolni az asztalt. Ez a módszer akkor sem hatékony, ha nagyon kevés műveletet végeznek a véges mezőben, mert az ember több időt tölt a táblázat kiszámításával, mint a tényleges számítás során.

Példák

Legyen α ∈ GF (2 ³ ) az x ³ + x ² + 1 primitív polinom gyökere . A mező elemeinek hagyományos ábrázolása polinomként α 2 vagy annál kisebb fokú.

A mező Zech logaritmusainak táblázata Z (−∞) = 0 , Z (0) = , Z (1) = 5 , Z (2) = 3 , Z (3) = 2 , Z (4) = 6 , Z (5) = 1 és Z (6) = 4 . Az α multiplikatív sorrendje 7, tehát az exponenciális ábrázolás a 7 modulo egész számokkal működik.

Mivel α x ³ + x ² + 1 gyöke, ez azt jelenti, hogy α ³ + α ² + 1 = 0 , vagy ha emlékeztetünk arra, hogy mivel minden együttható GF (2) -ben van, a kivonás megegyezik az összeadással, α ³ = α ² + 1 .

Az exponenciálisból a polinom reprezentációba való átváltást a

${\ displaystyle \ alpha ^ {3} = \ alpha ^ {2} +1}$ (a fentiek szerint)

${\ 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} + \ alfa = \ alfa ^ {2} +1+ \ alfa ^ {2} + \ alpha = \ alfa +1}$

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

Zech logaritmusok használata az α ⁶ + α ³ kiszámításához :

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

vagy hatékonyabban:

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

és annak ellenőrzése a polinomiábrázolásban:

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

Lásd még

• Gauss-féle logaritmus
• Ír logaritmus , Percy Ludgate empirikusan levezetett hasonló technika
• Véges mező számtani
• Logaritmus táblázat

Hivatkozások

További irodalom

• Fletcher, Alan; Miller, Jeffrey Charles Percy ; Rosenhead, Louis (1946) [1943]. Matematikai táblázatok indexe (1 szerk.). Blackwell Scientific Publications Ltd. , Oxford / McGraw-Hill , New York.
• Conway, John Horton (1968). Templomház, Robert F .; Herz, J.-C. (szerk.). Msgstr "A véges mezőkre vonatkozó információk táblázata". Számítógépek a matematikai kutatásban . Amszterdam: North-Holland Publishing Company : 37–50. MR   0237467 .
• Lam, Clement Wing Hong ; McKay, John KS (1973-11-01). "469. algoritmus: Aritmetika egy véges mező fölött [A1]". Az ACM kommunikációja . Az ACM (CALGO) összegyűjtött algoritmusai. Számítástechnikai Gépek Szövetsége (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) (német nyelven). Alling-Biburg, Németország. Archiválva (PDF) az eredetiből, 2018-07-14 . Letöltve: 2018-07-14 .