Zech logarithms are used to implement addition in finite fields when elements are represented as powers of a generator
Contents
Zech logarithms are named after Julius Zech, and are also called Jacobi logarithms, after C. G. J. Jacobi who used them for number theoretic investigations (C. G. J. Jacoby, "Über die Kreistheilung und ihre Anwendung auf die Zahlentheorie", in Gesammelte Werke, Vol.6, pp. 254–274).
Definition
If
or equivalently by
The choice of base
To be more precise,
where
Using the Zech logarithm, finite field arithmetic can be done in the exponential representation:
These formulas remain true with our conventions with the symbol
This can be extended to arithmetic of the projective line by introducing another symbol
Notice that for fields of characteristic two,
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 α ∈ GF(23) be a root of the primitive polynomial x3 + x2 + 1. The traditional representation of elements of this field is as polynomials in α of degree 2 or less.
A table of Zech logarithms for this field are Z(−∞) = 0, Z(0) = −∞, Z(1) = 5, Z(2) = 3, Z(3) = 2, Z(4) = 6, Z(5) = 1, and Z(6) = 4. The multiplicative order of α is 7, so the exponential representation works with integers modulo 7.
Since α is a root of x3 + x2 + 1 then that means α3 + α2 + 1 = 0, or if we recall that since all coefficients are in GF(2), subtraction is the same as addition, we obtain α3 = α2 + 1.
The conversion from exponential to polynomial representations is given by
Using Zech logarithms to compute α6 + α3:
or, more efficiently,
and verifying it in the polynomial representation: