Zech's logarithms
Encyclopedia
Zech's logarithms are used with finite field
s 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.
Zech logarithms are also called Jacobi Logarithm, after Jacobi who used them for number theoretic investigations
(C.G.J.Jacoby, "Uber die Kreistheilung und ihre Anwendung auf die Zahlentheorie, in Gesammelte Werke, Vol.6, pp. 254–274).
Use of Zech's logarithm for solving quadratic and cubic equations which may be of interest for coding applications can be found in
Let
be a primitive element of a finite field, then 
, the Zech logarithm of an integer 
may be defined such that
That is,
where the logarithm is taken to the base
. Note that if 
is the minus one element of the field, then 
is undefined (since that would involve the logarithm of zero). This definition of 
is analogous to the real-valued function used to implement addition in the Logarithmic Number System
(LNS), and may be used to implement similar hardware for a finite-field LNS.
Zech logarithms are also used when finite field elements are represented exponentially:
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
by the primitive polynomial as such:
(as shown above)
These polynomials are known as the Zech's logarithms for their corresponding powers of α. The representation of all elements of GF(23) is
We find that, using similar calculations to those above, that the Zech's logarithms for
are equal to
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
s to reduce a high-degree
Degree (mathematics)
In mathematics, there are several meanings of degree depending on the subject.- Unit of angle :A degree , usually denoted by ° , is a measurement of a plane angle, representing 1⁄360 of a turn...
polynomial that is not in the field to an element in the field (thus having a lower degree). Unlike the traditional logarithm
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
, the Zech's logarithm of a polynomial provides an equivalence — it does not alter the value.
Zech logarithms are also called Jacobi Logarithm, after Jacobi who used them for number theoretic investigations
(C.G.J.Jacoby, "Uber die Kreistheilung und ihre Anwendung auf die Zahlentheorie, in Gesammelte Werke, Vol.6, pp. 254–274).
Use of Zech's logarithm for solving quadratic and cubic equations which may be of interest for coding applications can be found in
Let
be a primitive element of a finite field, then , the Zech logarithm of an integer may be defined such thatThat is,
where the logarithm is taken to the base
. Note that if is the minus one element of the field, then is undefined (since that would involve the logarithm of zero). This definition of is analogous to the real-valued function used to implement addition in the Logarithmic Number SystemLogarithmic Number System
A logarithmic number system is an arithmetic system used for representing real numbers in computer and digital hardware, especially for digital signal processing.-Theory:...
(LNS), and may be used to implement similar hardware for a finite-field LNS.
Zech logarithms are also used when finite field elements are represented exponentially:
Polynomial basis
Let α ∈ GF(23) be a root of the primitive polynomialPrimitive polynomial
In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF...
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
by the primitive polynomial as such:
(as shown above)These polynomials are known as the Zech's logarithms for their corresponding powers of α. The representation of all elements of GF(23) is
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
are equal to