Zech's logarithm explained

Zech logarithms are used to implement addition in finite fields when elements are represented as powers of a generator

\alpha .

Zech logarithms are named after Julius Zech, and are also called Jacobi logarithms, after Carl G. J. Jacobi who used them for number theoretic investigations.

Definition

\alpha of a finite field, the Zech logarithm relative to the base \alpha is defined by the equation\alpha ^{Z _{\alpha(n)}} = 1 + \alpha ^{n,} which is often rewritten asZ _{\alpha(n)} = log _{\alpha(1} + \alpha ^{n).} The choice of base \alpha is usually dropped from the notation when it is clear from the context.

To be more precise,

Z _{\alpha} is a function on the integers modulo the multiplicative order of \alpha , and takes values in the same set. In order to describe every element, it is convenient to formally add a new symbol -inf ty , along with the definitions\alpha ^{-infty} = 0 n + ( -inf ty) = -inf ty Z _{\alpha(-infty)} = 0 Z _{\alpha(e)} = -inf ty where e is an integer satisfying \alpha ^{e} = -1 , that is e =0 for a field of characteristic 2, and e = (q -1)/(2) for a field of odd characteristic with q elements.

Using the Zech logarithm, finite field arithmetic can be done in the exponential representation:

\alpha ^{m} + \alpha ^{n} = \alpha ^{m} ⋅ ( 1 + \alpha ^{n-m} ) = \alpha ^{m} ⋅ \alpha ^{Z(n-m)} = \alpha ^{m} - \alpha ^{n} = ( -1 ) ⋅ \alpha ^{n} = \alpha ^{e} ⋅ \alpha ^{n} = \alpha ^{e+n} \alpha ^{m} - \alpha ^{n} = \alpha ^{m} + ( - \alpha ^{n)} = \alpha ^{m} \alpha ^{m} ⋅ \alpha ^{n} = \alpha ^{m+n} \left( \alpha ^{m} \right) ^{-1} = \alpha ^{-m} \alpha ^{m} / \alpha ^{n} = \alpha ^{m} ⋅ \left( \alpha ^{n} \right) ^{-1} = \alpha ^{m} These formulas remain true with our conventions with the symbol -inf ty , with the caveat that subtraction of -inf ty is undefined. In particular, the addition and subtraction formulas need to treat m = -inf ty as a special case.

This can be extended to arithmetic of the projective line by introducing another symbol

+inf ty satisfying \alpha ^{+infty} = inf ty and other rules as appropriate.

For fields of characteristic 2,

Z _{\alpha(n)} = m \iff Z _{\alpha(m)} = n .

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

\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

Using Zech logarithms to compute α^ 6 + α^ 3:

\alpha ^{6} + \alpha ^{3} = \alpha ^{6} = \alpha ^{6} = \alpha ^{6} = \alpha ^{12} = \alpha ^{5,} or, more efficiently,\alpha ^{6} + \alpha ^{3} = \alpha ^{3} = \alpha ^{3} = \alpha ^{5,} and verifying it in the polynomial representation:\alpha ^{6} + \alpha ^{3} = (\alpha ^{2} + \alpha) + (\alpha ^{2} + 1 ) = \alpha + 1 = \alpha ^{5.}

See also

• Gaussian logarithm
• Irish logarithm, a similar technique derived empirically by Percy Ludgate
• Finite field arithmetic
• Logarithm table

Further reading

• Book: An Index of Mathematical Tables . Alan . Fletcher . Jeffrey Charles Percy . Miller . Jeffrey Charles Percy Miller . Louis . Rosenhead . Louis Rosenhead . 1946 . 1943 . Blackwell Scientific Publications Ltd., Oxford / McGraw-Hill, New York . 1.
• A tabulation of some information concerning finite fields . John Horton . Conway . John Horton Conway . Robert F. . Churchhouse . J.-C. . Herz . 0237467 . Computers in Mathematical Research . 1968 . 37–50 . . Amsterdam . 12.20 (10.00) -->.
• Collected Algorithms of the ACM (CALGO) . Algorithm 469: Arithmetic over a finite field [A1] . toms/469 . Clement Wing Hong . Lam . Clement Wing Hong Lam . John K. S. . McKay . John K. S. McKay . . 0001-0782 . Association for Computing Machinery (ACM) . 16 . 11 . 699 . 1973-11-01 . 10.1145/355611.362544 . 62794130 . free . https://web.archive.org/web/20180714103520/http://calgo.acm.org/ --> https://web.archive.org/web/20180714103459/https://people.sc.fsu.edu/~jburkardt/html/toms.html --> https://web.archive.org/web/20180714105025/http://www.netlib.org/toms-2014-06-10/620 -->
• Web site: C. F. Gauß und die Logarithmen . German . Klaus . Kühn . Alling-Biburg, Germany . 2008 . 2018-07-14 . live . https://web.archive.org/web/20180714030921/http://www.rechenschieber.org/Gauss.pdf . 2018-07-14.