Zech's logarithms

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 an integer $n$ may be defined such that

α Z (n) = 1 + α n

That is, $Z (n) = log(1 + α n)$ where the logarithm is taken to the base $α$ . Note that if $α n$ is the minus one element of the field, then $Z (n)$ is undefined (since that would involve the logarithm of zero).

[edit] Examples

[edit] 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:

α 3 = α 2 + 1

(as shown above)

α 4 = α 3 α = (α 2 + 1)α = α 3 + α = α 2 + α + 1

α 5 = α 4 α = (α 2 + α + 1)α = α 3 + α 2 + α = α 2 + 1 + α 2 + α = α + 1

α 6 = α 5 α = (α + 1)α = α 2 + α

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 \,\}.$

[edit] 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

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