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.

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$ isthe minus one element of the field, then $Z(n)$ is undefined (since that would involvethe logarithm of zero).

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 polynomials are known as the Zech's logarithms for their corresponding powers of α. The representation of all elements of GF(2³) is

:$\{,\; 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 Zech's logarithms for

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

are equal to

: