Zech's logarithms

Zech's logarithms are used with finite fields to reduce a high-degree polynomial that is not in the field to an element in the field (thus having a lower degree). Unlike the traditional logarithm, the Zech's logarithm of a polynomial provides an equivalence — it does not alter the value.

Zech logarithms are also called Jacobi Logarithm, after Jacobi who used them for number theoretic investigations (C.G.J.Jacoby, "Uber die Kreistheilung und ihre Anwendung auf die Zahlentheorie, in Gesammelte Werke, Vol.6, pp. 254–274).

Use of Zech's logarithm for solving quadratic and cubic equations which may be of interest for coding applications can be found in

Let $\alpha$ be a primitive element of a finite field, then $Z(n)$, the Zech logarithm of an integer $n$ may be defined such that

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

That is, $Z(n) = \log(1 + \alpha^n)$ where the logarithm is taken to the base $\alpha$. Note that if $\alpha^n$ is the minus one element of the field, then $Z(n)$ is undefined (since that would involve the logarithm of zero). This definition of $Z(n)$ is analogous to the real-valued function used to implement addition in the Logarithmic Number System (LNS), and may be used to implement similar hardware for a finite-field LNS.

Zech logarithms are also used when finite field elements are represented exponentially:

$\alpha^n + \alpha^m = \alpha^n \cdot (1 + \alpha^{m-n}) = \alpha^n \cdot \alpha^{Z(m-n)} = \alpha^{n + Z(m-n)}$

Examples

Polynomial basis

Let α ∈ GF(2³) be a root of the primitive polynomial x³ + x² + 1. Thus all powers of α higher than 2 can be reduced.

Since α is a root of x³ + x² + 1 then that means α³ + α² + 1 = 0, or if we recall that since all coefficients are in GF(2), subtraction is the same as addition, we obtain α³ = α² + 1.

Now we can easily reduce the set

$\{\, 0, 1, \alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6 \,\}$

by the primitive polynomial as such:

$\alpha^3 = \alpha^2 + 1$ (as shown above)

$\alpha^4 = \alpha^3 \alpha = (\alpha^2 + 1)\alpha = \alpha^3 + \alpha = \alpha^2 + \alpha + 1$

$\alpha^5 = \alpha^4 \alpha = (\alpha^2 + \alpha + 1)\alpha = \alpha^3 + \alpha^2 + \alpha = \alpha^2 + 1 + \alpha^2 + \alpha = \alpha + 1$

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

These are also sometimes called the (base $\alpha$) anti-logarithms of the corresponding powers of the generating element. We see that in this case the Zech logarithms are: Z(1)=5, Z(2)=3, Z(3)=2, Z(4)=6, Z(5)=1 and Z(6)=4. For example the value of Z(2)=3 follows from the equation $1+\alpha^2=\alpha^3.$

The polynomial representations of all elements of GF(2³) are

$\{\, 0, 1, \alpha, \alpha^2, \alpha^2 + 1, \alpha^2 + \alpha + 1, \alpha + 1, \alpha^2 + \alpha \,\}.$

Normal basis

The normal basis representation of elements in this set will only use the 3 elements β, β², and β⁴. We can see by looking at the above example that if we set β = α then β² = α² and β⁴ = α² + α + 1, and thus β, β², and β⁴ are linearly independent and form a normal basis. So all elements in the field can be written as linear combinations of β, β², and β⁴.

We find that, using similar calculations to those above that the presentations of the elements

$\{\, 0, 1, \alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6 \,\}$

in terms of this normal basis are

$\{\, 0, \beta^4 + \beta^2 + \beta, \beta, \beta^2, \beta^4 + \beta, \beta^4, \beta^4 + \beta^2, \beta^2 + \beta \,\}.$