Zech's logarithm


Zech logarithms are used to implement addition in finite fields when elements are represented as powers of a generator.
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.

Definition

Given a primitive element of a finite field, the Zech logarithm relative to the base is defined by the equation
which is often rewritten as
The choice of base is usually dropped from the notation when it is clear from the context.
To be more precise, is a function on the integers modulo the multiplicative order of, and takes values in the same set. In order to describe every element, it is convenient to formally add a new symbol, along with the definitions
where is an integer satisfying, that is for a field of characteristic 2, and for a field of odd characteristic with elements.
Using the Zech logarithm, finite field arithmetic can be done in the exponential representation:
These formulas remain true with our conventions with the symbol, with the caveat that subtraction of is undefined. In particular, the addition and subtraction formulas need to treat as a special case.
This can be extended to arithmetic of the projective line by introducing another symbol satisfying and other rules as appropriate.
For fields of characteristic 2,

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 be a root of the primitive [polynomial (field theory)|primitive polynomial]. The traditional representation of elements of this field is as polynomials in of degree or less.
Here is a table of Zech logarithms for this field.
The multiplicative order of is, so the exponential representation works with integers modulo.
Since is a root of then that means, or if we recall that since all coefficients are in, subtraction is the same as addition, we obtain.
The conversion from exponential to polynomial representations is given by

Using Zech logarithms to compute :
or, more efficiently,
and verifying it in the polynomial representation:

Visualization

Given a prime power and a primitive element of, one can visualize the Zech logarithm by plotting all elements of in a directed graph, :
The edges in correspond to the mappings in the Zech logarithm function: since, an edge connecting node to effectively connects the exponent to the exponent.
Here is, where is a root of, and the powers of are placed in counterclockwise order:


If one draws an edge instead of for every in, where is any fixed element, one obtains a graph. The standard graph corresponds to. The graph consists of self-loops. For any, the graph appears identical to, except that all edges are rotated by around the center node.
Here is, which differs from by a rotation of :


Each graph visualizes the permutation. The set of these permutations forms an Elementary abelian group of order . The rotational symmetry of the graphs for elegantly captures the algebraic indistinguishability of the non-zero elements in an elementary abelian group.
If and are both primitive elements of, then the graphs and are identical if and only if and are roots of the same primitive polynomial in. Therefore, the number of distinct graphs equals, where is Euler's totient function. Equivalently, there exist distinct Zech logarithm tables for a given field size.
If and are multiplicative inverses of each other, then and are reflections of each other.
When is odd, contains a "diagonal" edge that connects the node to .
Here are the graphs for all such that the graph remains invariant across all primitive elements :