From Wikipedia, the free encyclopedia

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 α be a primitive element of a finite field, then Z(n), the Zech logarithm of n may be defined such that

α^Z(n) = 1 + αⁿ

That is, Z(n) = log(1 + αⁿ) where the logarithm is taken to the base α.

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

by the primitive polynomial as such:

α³ = α² + 1 (as shown above)

α⁴ = α³α = (α² + 1)α = α³ + α = α² + α + 1

α⁵ = α⁴α = (α² + α + 1)α = α³ + α² + α = α² + 1 + α² + α = α + 1

α⁶ = α⁵α = (α + 1)α = α² + α

These polynomials are known as the Zech's logarithms for their corresponding powers of α. The representation of all elements of GF(2³) is

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

are equal to