|
|
|
|
|
Zech's LogarithmsZech'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. Examples 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 \,\}. 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 \,\}.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|