Zech logarithms are used to implement addition in
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s when elements are represented as powers of a generator
.
Zech logarithms are named after
Julius Zech
Julius August Christoph Zech (24 February 1821 Stuttgart, Germany − 13 July 1864 Berg) was a German astronomer and mathematician.
In 1849, Zech published a table of logarithms; as a result, Zech's logarithm, Zech logarithms for finite fields ...
,
and are also called Jacobi logarithms,
after
Carl G. J. Jacobi who used them for
number theoretic investigations.
Definition
Given a
primitive element of a finite field, the Zech logarithm relative to the base
is defined by the equation
:
which is often rewritten as
:
The choice of base
is usually dropped from the notation when it is clear from the context.
To be more precise,
is a function on the integers modulo the multiplicative order of
, and takes values in the same set. In order to describe every element, it is convenient to formally add a new symbol
, along with the definitions
:
:
:
:
where
is an integer satisfying
, that is
for a field of
characteristic 2, and
for a field of odd characteristic with
elements.
Using the Zech logarithm, finite field arithmetic can be done in the exponential representation:
:
:
:
:
:
:
These formulas remain true with our conventions with the symbol
, with the caveat that subtraction of
is undefined. In particular, the addition and subtraction formulas need to treat
as a special case.
This can be extended to arithmetic of the
projective line
In mathematics, a projective line is, roughly speaking, the extension of a usual line by a point called a ''point at infinity''. The statement and the proof of many theorems of geometry are simplified by the resultant elimination of special cases; ...
by introducing another symbol
satisfying
and other rules as appropriate.
For fields of characteristic two,
:
.
Uses
For sufficiently small finite fields, a table of Zech logarithms allows an especially efficient implementation of all finite field arithmetic in terms of a small number of integer addition/subtractions and table look-ups.
The utility of this method diminishes for large fields where one cannot efficiently store the table. This method is also inefficient when doing very few operations in the finite field, because one spends more time computing the table than one does in actual calculation.
Examples
Let be a root of the
primitive polynomial . The traditional representation of elements of this field is as polynomials in α of degree 2 or less.
A table of Zech logarithms for this field are , , , , , , , and . The multiplicative order of ''α'' is 7, so the exponential representation works with integers modulo 7.
Since ''α'' is a root of then that means , or if we recall that since all coefficients are in GF(2), subtraction is the same as addition, we obtain .
The conversion from exponential to polynomial representations is given by
:
(as shown above)
:
:
:
Using Zech logarithms to compute :
:
,
or, more efficiently,
:
,
and verifying it in the polynomial representation:
:
.
See also
*
Gaussian logarithm
In mathematics, addition and subtraction logarithms or Gaussian logarithms can be utilized to find the logarithms of the Addition, sum and Subtraction, difference of a pair of values whose logarithms are known, without knowing the values themselves ...
*
Irish logarithm, a similar technique derived empirically by Percy Ludgate
*
Finite field arithmetic In mathematics, finite field arithmetic is arithmetic in a finite field (a field containing a finite number of elements) contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.
There are infinitel ...
*
Logarithm table
In mathematics, the common logarithm is the logarithm with base 10. It is also known as the decadic logarithm and as the decimal logarithm, named after its base, or Briggsian logarithm, after Henry Briggs, an English mathematician who pioneered i ...
References
Further reading
*
*
*
https://web.archive.org/web/20180714105025/http://www.netlib.org/toms-2014-06-10/620 -->
*
{{DEFAULTSORT:Zech's Logarithms
Linear algebra
Finite fields