Editing Zech's logarithm

{{short description|Tool for a fast finite-field arithmetic}}
{{Use dmy dates|date=May 2019|cs1-dates=y}}
'''Zech logarithms''' are used to implement addition in [[finite field]]s when elements are represented as powers of a generator <math>\alpha</math>.

Zech logarithms are named after [[Julius Zech]],<ref name="Zech_1849"/><ref name="Zech_1863"/><ref name="Zech_1892"/><ref name="Zech_1910"/> and are also called '''Jacobi logarithms''',<ref name="Lidl_1997"/> after [[Carl Gustav Jacob Jacobi|Carl G. J. Jacobi]] who used them for [[number theoretic]] investigations.<ref name="Jacoby_1846"/>

==Definition==
Given a [[Primitive element (finite field)|primitive element]] <math>\alpha</math> of a finite field, the Zech logarithm relative to the base <math>\alpha</math> is defined by the equation
:<math>\alpha^{Z_\alpha(n)} = 1 + \alpha^n,</math>
which is often rewritten as
:<math>Z_\alpha(n) = \log_\alpha(1 + \alpha^n).</math>
The choice of base <math>\alpha</math> is usually dropped from the notation when it is clear from the context.

To be more precise, <math>Z_\alpha</math> is a [[function (mathematics)|function]] on the [[integer]]s [[modular arithmetic|modulo]] the multiplicative order of <math>\alpha</math>, and takes values in the same set. In order to describe every element, it is convenient to formally add a new symbol <math>-\infty</math>, along with the definitions
:<math>\alpha^{-\infty} = 0</math>
:<math>n + (-\infty) = -\infty</math> 
:<math>Z_\alpha(-\infty) = 0</math>
:<math>Z_\alpha(e) = -\infty</math>
where <math>e</math> is an integer satisfying <math>\alpha^e = -1</math>, that is <math>e=0</math> for a [[field (mathematics)|field]] of [[characteristic (algebra)|characteristic]] 2, and <math>e = \frac{q-1}{2}</math> for a field of [[parity (mathematics)|odd]] characteristic with <math>q</math> elements.

Using the Zech logarithm, finite field arithmetic can be done in the exponential representation:
:<math>\alpha^m + \alpha^n = \alpha^m \cdot (1 + \alpha^{n-m}) = \alpha^m \cdot \alpha^{Z(n-m)} = \alpha^{m + Z(n-m)} </math>
:<math>-\alpha^n = (-1) \cdot \alpha^n = \alpha^e \cdot \alpha^n = \alpha^{e+n}</math>
:<math>\alpha^m - \alpha^n = \alpha^m + (-\alpha^n) = \alpha^{m + Z(e+n-m)} </math>
:<math>\alpha^m \cdot \alpha^n = \alpha^{m+n}</math>
:<math>\left( \alpha^m \right)^{-1} = \alpha^{-m}</math>
:<math>\alpha^m / \alpha^n = \alpha^m \cdot \left( \alpha^n \right)^{-1} = \alpha^{m - n}</math>
These formulas remain true with our conventions with the symbol <math>-\infty</math>, with the caveat that subtraction of <math>-\infty</math> is undefined. In particular, the addition and subtraction formulas need to treat <math>m = -\infty</math> as a special case.

This can be extended to arithmetic of the [[projective line]] by introducing another symbol <math>+\infty</math> satisfying <math>\alpha^{+\infty} = \infty</math> and other rules as appropriate.

For fields of characteristic 2,
:<math>Z_\alpha(n) = m \iff Z_\alpha(m) = n</math>.

==Uses==
For sufficiently small finite fields, a table of Zech logarithms allows an especially efficient implementation of  all finite field arithmetic in terms of a small number of integer addition/subtractions and table look-ups.

The utility of this method diminishes for large fields where one cannot efficiently store the table. This method is also inefficient when doing very few operations in the finite field, because one spends more time computing the table than one does in actual calculation.

==Examples==

Let {{nowrap|''α'' ∈ GF(2<sup>3</sup>)}} be a [[root of a polynomial|root]] of the [[primitive polynomial (field theory)|primitive polynomial]] {{nowrap|''x''<sup>3</sup> + ''x''<sup>2</sup> + 1}}.  The traditional representation of elements of this field is as [[polynomial]]s in α of [[degree of a polynomial|degree]] 2 or less.

A table of Zech logarithms for this field are {{nowrap|1=''Z''(−∞) = 0}}, {{nowrap|1=''Z''(0) = −∞}}, {{nowrap|1=''Z''(1) = 5}}, {{nowrap|1=''Z''(2) = 3}}, {{nowrap|1=''Z''(3) = 2}}, {{nowrap|1=''Z''(4) = 6}}, {{nowrap|1=''Z''(5) = 1}}, and {{nowrap|1=''Z''(6) = 4}}. The multiplicative order of ''α'' is 7, so the exponential representation works with integers modulo 7.

Since ''α'' is a root of {{nowrap|''x''<sup>3</sup> + ''x''<sup>2</sup> + 1}} then that means {{nowrap|1=''α''<sup>3</sup> + ''α''<sup>2</sup> + 1 = 0}}, or if we recall that since all coefficients are in&nbsp;GF(2), subtraction is the same as addition, we obtain {{nowrap|1=''α''<sup>3</sup> = ''α''<sup>2</sup> + 1}}.

The conversion from exponential to polynomial representations is given by
:<math>\alpha^3 = \alpha^2 + 1</math> (as shown above)
:<math>\alpha^4 = \alpha^3 \alpha = (\alpha^2 + 1)\alpha = \alpha^3 + \alpha = \alpha^2 + \alpha + 1</math>
:<math>\alpha^5 = \alpha^4 \alpha = (\alpha^2 + \alpha + 1)\alpha = \alpha^3 + \alpha^2 + \alpha = \alpha^2 + 1 + \alpha^2 + \alpha = \alpha + 1</math>
:<math>\alpha^6 = \alpha^5 \alpha = (\alpha + 1)\alpha = \alpha^2 + \alpha</math>

Using Zech logarithms to compute ''α''<sup>{{hairsp}}6</sup> + ''α''<sup>{{hairsp}}3</sup>:
:<math>\alpha^6 + \alpha^3 = \alpha^{6 + Z(-3)} = \alpha^{6 + Z(4)} = \alpha^{6 + 6} = \alpha^{12} = \alpha^5,</math>
or, more efficiently,
:<math>\alpha^6 + \alpha^3 = \alpha^{3 + Z(3)} = \alpha^{3 + 2} = \alpha^5,</math>
and verifying it in the polynomial representation:
:<math>\alpha^6 + \alpha^3 = (\alpha^2 + \alpha) + (\alpha^2 + 1) = \alpha + 1 = \alpha^5.</math>

==See also==
* [[Gaussian logarithm]]
* [[Irish logarithm]], a similar technique derived empirically by Percy Ludgate
* [[Finite field arithmetic]]
* [[Logarithm table]]

==References==
{{Reflist|refs=
<ref name="Zech_1849">{{cite book |title=Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen |language=German |author-first=Julius August Christoph |author-last=Zech |author-link=Julius August Christoph Zech |date=1849 |edition=Specially reprinted (from Vega–Hülße collection) 1st |location=Leipzig |publisher=[[Weidmann'sche Buchhandlung]] |url=https://catalog.hathitrust.org/Record/000448557 |access-date=2018-07-14 |url-status=live |archive-url=https://web.archive.org/web/20180714035149/https://catalog.hathitrust.org/Record/000448557 |archive-date=2018-07-14}} Also part of: {{cite book |title=Sammlung mathematischer Tafeln |language=German |author-first1=Georg |author-last1=Freiherr von Vega |author-link1=Georg Freiherr von Vega |editor-first1=Julius Ambrosius |editor-last1=Hülße |editor-link1=:de:Julius Ambrosius Hülße |editor-first2=Julius August Christoph |editor-last2=Zech |editor-link2=Julius August Christoph Zech |date=1849 |edition=Completely reworked |location=Leipzig |publisher=[[Weidmann'sche Buchhandlung]] |url=https://catalog.hathitrust.org/Record/000448019?type%5B%5D=author&lookfor%5B%5D=%22Zech%2C%20Julius%20August%20Christoph%2C%201821-1864.%22&ft= |access-date=2018-07-14 |url-status=live |archive-url=https://web.archive.org/web/20180714091525/https://catalog.hathitrust.org/Record/000448019?type%255B%255D=author&lookfor%255B%255D=%2522Zech%252C%2520Julius%2520August%2520Christoph%252C%25201821-1864.%2522&ft= |archive-date=2018-07-14|bibcode=1849smt..book.....V }}</ref>
<ref name="Zech_1863">{{cite book |title=Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen |language=German |author-first=Julius August Christoph |author-last=Zech |author-link=Julius August Christoph Zech |date=1863 |orig-year=1849 |edition=Specially reprinted (from Vega–Hülße collection) 2nd |location=Berlin |publisher=[[Weidmann'sche Buchhandlung]] |url=https://catalog.hathitrust.org/Record/000448562 |access-date=2018-07-13 |url-status=live |archive-url=https://web.archive.org/web/20180714091822/https://catalog.hathitrust.org/Record/000448562 |archive-date=2018-07-14}}</ref>
<ref name="Zech_1892">{{cite book |title=Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen |language=German |author-first=Julius August Christoph |author-last=Zech |author-link=Julius August Christoph Zech |date=1892 |orig-year=1849 |edition=Specially reprinted (from Vega–Hülße collection) 3rd |location=Berlin |publisher=[[Weidmann'sche Buchhandlung]] |url=https://catalog.hathitrust.org/Record/012310509 |access-date=2018-07-13 |url-status=live |archive-url=https://web.archive.org/web/20180714093934/https://catalog.hathitrust.org/Record/012310509 |archive-date=2018-07-14}}</ref>
<ref name="Zech_1910">{{cite book |title=Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen |language=German |author-first=Julius August Christoph |author-last=Zech |author-link=Julius August Christoph Zech |date=1910 |orig-year=1849 |edition=Specially reprinted (from Vega–Hülße collection) 4th |location=Berlin |publisher=[[Weidmann'sche Buchhandlung]] |url=https://catalog.hathitrust.org/Record/000448565 |access-date=2018-07-13 |url-status=live |archive-url=https://web.archive.org/web/20180714100452/https://catalog.hathitrust.org/Record/000448565 |archive-date=2018-07-14}}</ref>
<ref name="Lidl_1997">{{Cite book |author-last1=Lidl |author-first1=Rudolf |author-last2=Niederreiter |author-first2=Harald |author-link2=Harald Niederreiter |title=Finite Fields |edition=2nd |publisher=[[Cambridge University Press]] |isbn=978-0-521-39231-0 |date=1997 |url-access=registration |url=https://archive.org/details/finitefields0000lidl_a8r3 }}</ref>
<ref name="Jacoby_1846">{{cite journal |author-first=Carl Gustav Jacob |author-last=Jacoby |author-link=Carl Gustav Jacob Jacobi |title=Über die Kreistheilung und ihre Anwendung auf die Zahlentheorie |language=German |volume=1846 |number=30 |journal=[[Journal für die reine und angewandte Mathematik]] |date=1846 |pages=166–182 |issn=0075-4102 |url=http://eudml.org/doc/147283|doi=10.1515/crll.1846.30.166 |s2cid=120615565 }} (NB. Also part of "Gesammelte Werke", Volume 6, pages 254–274.)</ref>
}}

==Further reading==
* {{cite book |title=An Index of Mathematical Tables |author-first1=Alan |author-last1=Fletcher |author-first2=Jeffrey Charles Percy |author-last2=Miller |author-link2=Jeffrey Charles Percy Miller |author-first3=Louis |author-last3=Rosenhead |author-link3=Louis Rosenhead |date=1946 |orig-year=1943 |publisher=[[Blackwell Scientific Publications Ltd.]], Oxford / [[McGraw-Hill]], New York |edition=1<!-- there was a 2nd 2-volume edition in 1962 -->}}
* {{cite journal |title=A tabulation of some information concerning finite fields |author-first=John Horton |author-last=Conway |author-link=John Horton Conway |editor-first1=Robert F. |editor-last1=Churchhouse |editor-first2=J.-C. |editor-last2=Herz |mr=0237467 |journal=Computers in Mathematical Research |date=1968 |pages=37–50 |publisher=[[North-Holland Publishing Company]] |location=Amsterdam <!-- |id=12.20 (10.00) -->}}
* {{cite journal |series=Collected Algorithms of the ACM (CALGO) |title=Algorithm 469: Arithmetic over a finite field [A1] |id=toms/469 |author-first1=Clement Wing Hong |author-last1=Lam |author-link1=Clement Wing Hong Lam |author-first2=John K. S. |author-last2=McKay |author-link2=John K. S. McKay |journal=[[Communications of the ACM]] |issn=0001-0782 |publisher=[[Association for Computing Machinery]] (ACM) |volume=16 |issue=11 |page=699 |date=1973-11-01 |doi=10.1145/355611.362544 |s2cid=62794130 |doi-access=free }} [http://www.acm.org/calgo/<!-- https://web.archive.org/web/20180714103520/http://calgo.acm.org/ -->] [https://people.sc.fsu.edu/~jburkardt/html/toms.html<!-- https://web.archive.org/web/20180714103459/https://people.sc.fsu.edu/~jburkardt/html/toms.html -->] [http://www.netlib.org/toms-2014-06-10/620<!-- https://web.archive.org/web/20180714105025/http://www.netlib.org/toms-2014-06-10/620 -->]
* {{cite web |title=C. F. Gauß und die Logarithmen |language=German |author-first=Klaus |author-last=Kühn |location=Alling-Biburg, Germany |date=2008 |url=http://www.rechenschieber.org/Gauss.pdf |access-date=2018-07-14 |url-status=live |archive-url=https://web.archive.org/web/20180714030921/http://www.rechenschieber.org/Gauss.pdf |archive-date=2018-07-14}}

{{DEFAULTSORT:Zech's Logarithms}}
[[Category:Linear algebra]]
[[Category:Finite fields]]