Zech's logarithm

Zech logarithms are used to implement addition in finite fields when elements are represented as powers of a generator ${\displaystyle \alpha }$.

Zech logarithms are named after Julius Zech, and are also called Jacobi logarithms, after Carl G. J. Jacobi who used them for number theoretic investigations.

Given a primitive element ${\displaystyle \alpha }$ of a finite field, the Zech logarithm relative to the base ${\displaystyle \alpha }$ is defined by the equation $${\displaystyle \alpha ^{Z_{\alpha }(n)}=1+\alpha ^{n},}$$ which is often rewritten as $${\displaystyle Z_{\alpha }(n)=\log _{\alpha }(1+\alpha ^{n}).}$$ The choice of base ${\displaystyle \alpha }$ is usually dropped from the notation when it is clear from the context.

To be more precise, ${\displaystyle Z_{\alpha }}$ is a function on the integers modulo the multiplicative order of ${\displaystyle \alpha }$, and takes values in the same set. In order to describe every element, it is convenient to formally add a new symbol ${\displaystyle -\infty }$, along with the definitions $${\displaystyle \alpha ^{-\infty }=0}$$ $${\displaystyle n+(-\infty )=-\infty }$$ $${\displaystyle Z_{\alpha }(-\infty )=0}$$ $${\displaystyle Z_{\alpha }(e)=-\infty }$$ where ${\displaystyle e}$ is an integer satisfying ${\displaystyle \alpha ^{e}=-1}$, that is ${\displaystyle e=0}$ for a field of characteristic 2, and ${\displaystyle e={\frac {q-1}{2}}}$ for a field of odd characteristic with ${\displaystyle q}$ elements.

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

This can be extended to arithmetic of the projective line by introducing another symbol ${\displaystyle +\infty }$ satisfying ${\displaystyle \alpha ^{+\infty }=\infty }$ and other rules as appropriate.

For fields of characteristic 2, $${\displaystyle Z_{\alpha }(n)=m\iff Z_{\alpha }(m)=n.}$$

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.