Related Searches


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


Polynomial basis

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

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.

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(23) 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 β, β2, and β4. We can see by looking at the above example that if we set β = α then β2 = α2 and β4 = α2 + α + 1, and thus β, β2, and β4 are linearly independent and form a normal basis. So all elements in the field can be written as linear combinations of β, β2, and β4.

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

Search another word or see Zechon Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature