Zech's logarithm

Zech logarithms are used to implement addition in finite fields when elements are represented as powers of a generator α {\displaystyle \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

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

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

Using the Zech logarithm, finite field arithmetic can be done in the exponential representation: α m + α n = α m ⋅ ( 1 + α n − m ) = α m ⋅ α Z ( n − m ) = α m + Z ( n − m ) {\displaystyle \alpha ^{m}+\alpha ^{n}=\alpha ^{m}\cdot (1+\alpha ^{n-m})=\alpha ^{m}\cdot \alpha ^{Z(n-m)}=\alpha ^{m+Z(n-m)}} − α n = ( − 1 ) ⋅ α n = α e ⋅ α n = α e + n {\displaystyle -\alpha ^{n}=(-1)\cdot \alpha ^{n}=\alpha ^{e}\cdot \alpha ^{n}=\alpha ^{e+n}} α m − α n = α m + ( − α n ) = α m + Z ( e + n − m ) {\displaystyle \alpha ^{m}-\alpha ^{n}=\alpha ^{m}+(-\alpha ^{n})=\alpha ^{m+Z(e+n-m)}} α m ⋅ α n = α m + n {\displaystyle \alpha ^{m}\cdot \alpha ^{n}=\alpha ^{m+n}} ( α m ) − 1 = α − m {\displaystyle \left(\alpha ^{m}\right)^{-1}=\alpha ^{-m}} α m / α n = α m ⋅ ( α n ) − 1 = α m − n {\displaystyle \alpha ^{m}/\alpha ^{n}=\alpha ^{m}\cdot \left(\alpha ^{n}\right)^{-1}=\alpha ^{m-n}} These formulas remain true with our conventions with the symbol − ∞ {\displaystyle -\infty }, with the caveat that subtraction of − ∞ {\displaystyle -\infty } is undefined. In particular, the addition and subtraction formulas need to treat m = − ∞ {\displaystyle m=-\infty } as a special case.

This can be extended to arithmetic of the projective line by introducing another symbol + ∞ {\displaystyle +\infty } satisfying α + ∞ = ∞ {\displaystyle \alpha ^{+\infty }=\infty } and other rules as appropriate.

For fields of characteristic 2, Z α ( n ) = m ⟺ Z α ( m ) = n . {\displaystyle 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 α ∈ G F ( 2 3 ) {\displaystyle \alpha \in \mathrm {GF} (2^{3})} be a root of the primitive polynomial x 3 + x 2 + 1 {\displaystyle x^{3}+x^{2}+1}. The traditional representation of elements of this field is as polynomials in α {\displaystyle \alpha } of degree 2 {\displaystyle 2} or less.

Here is a table of Zech logarithms for this field.

Z α ( − ∞ ) = 0 {\displaystyle Z_{\alpha }(-\infty )=0} Z α ( 0 ) = − ∞ {\displaystyle Z_{\alpha }(0)=-\infty } Z α ( 1 ) = 5 {\displaystyle Z_{\alpha }(1)=5} Z α ( 2 ) = 3 {\displaystyle Z_{\alpha }(2)=3} Z α ( 3 ) = 2 {\displaystyle Z_{\alpha }(3)=2} Z α ( 4 ) = 6 {\displaystyle Z_{\alpha }(4)=6} Z α ( 5 ) = 1 {\displaystyle Z_{\alpha }(5)=1} Z α ( 6 ) = 4 {\displaystyle Z_{\alpha }(6)=4}

The multiplicative order of α {\displaystyle \alpha } is 7 {\displaystyle 7}, so the exponential representation works with integers modulo 7 {\displaystyle 7}.

Since α {\displaystyle \alpha } is a root of x 3 + x 2 + 1 {\displaystyle x^{3}+x^{2}+1} then that means α 3 + α 2 + 1 = 0 {\displaystyle \alpha ^{3}+\alpha ^{2}+1=0}, or if we recall that since all coefficients are in G F ( 2 ) {\displaystyle \mathrm {GF} (2)}, subtraction is the same as addition, we obtain α 3 = α 2 + 1 {\displaystyle \alpha ^{3}=\alpha ^{2}+1}.

The conversion from exponential to polynomial representations is given by α 3 = α 2 + 1 {\displaystyle \alpha ^{3}=\alpha ^{2}+1} (as shown above) α 4 = α 3 α = ( α 2 + 1 ) α = α 3 + α = α 2 + α + 1 {\displaystyle \alpha ^{4}=\alpha ^{3}\alpha =(\alpha ^{2}+1)\alpha =\alpha ^{3}+\alpha =\alpha ^{2}+\alpha +1} α 5 = α 4 α = ( α 2 + α + 1 ) α = α 3 + α 2 + α = α 2 + 1 + α 2 + α = α + 1 {\displaystyle \alpha ^{5}=\alpha ^{4}\alpha =(\alpha ^{2}+\alpha +1)\alpha =\alpha ^{3}+\alpha ^{2}+\alpha =\alpha ^{2}+1+\alpha ^{2}+\alpha =\alpha +1} α 6 = α 5 α = ( α + 1 ) α = α 2 + α {\displaystyle \alpha ^{6}=\alpha ^{5}\alpha =(\alpha +1)\alpha =\alpha ^{2}+\alpha }

Using Zech logarithms to compute α 6 + α 3 {\displaystyle \alpha ^{6}+\alpha ^{3}}: α 6 + α 3 = α 6 + Z ( − 3 ) = α 6 + Z ( 4 ) = α 6 + 6 = α 12 = α 5 , {\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{6+Z(-3)}=\alpha ^{6+Z(4)}=\alpha ^{6+6}=\alpha ^{12}=\alpha ^{5},} or, more efficiently, α 6 + α 3 = α 3 + Z ( 3 ) = α 3 + 2 = α 5 , {\displaystyle \alpha ^{6}+\alpha ^{3}=\alpha ^{3+Z(3)}=\alpha ^{3+2}=\alpha ^{5},} and verifying it in the polynomial representation: α 6 + α 3 = ( α 2 + α ) + ( α 2 + 1 ) = α + 1 = α 5 . {\displaystyle \alpha ^{6}+\alpha ^{3}=(\alpha ^{2}+\alpha )+(\alpha ^{2}+1)=\alpha +1=\alpha ^{5}.}

Visualization

Given a prime power q = p n {\displaystyle q=p^{n}} and a primitive element α {\displaystyle \alpha } of G F ( q ) {\displaystyle \mathrm {GF} (q)}, one can visualize the Zech logarithm Z α {\displaystyle Z_{\alpha }} by plotting all elements of G F ( q ) {\displaystyle \mathrm {GF} (q)} in a directed graph, G α ( q ) {\displaystyle G_{\alpha }(q)}:

Place the element 0 {\displaystyle 0} at the center.
Arrange the non-zero elements α , α 2 , … , α q − 1 = 1 {\displaystyle \alpha ,\alpha ^{2},\dots ,\alpha ^{q-1}=1} sequentially as equally spaced nodes around a circle, with 1 {\displaystyle 1} at the top.
Draw a directed edge x → x + 1 {\displaystyle x\to x+1} for every x {\displaystyle x} in G F ( q ) {\displaystyle \mathrm {GF} (q)}.

The edges in G α ( q ) {\displaystyle G_{\alpha }(q)} correspond to the mappings in the Zech logarithm function: since α Z ( n ) = α n + 1 {\displaystyle \alpha ^{Z(n)}=\alpha ^{n}+1}, an edge connecting node α n {\displaystyle \alpha ^{n}} to α n + 1 {\displaystyle \alpha ^{n}+1} effectively connects the exponent n {\displaystyle n} to the exponent Z ( n ) {\displaystyle Z(n)}.

Here is G α ( 8 ) {\displaystyle G_{\alpha }(8)}, where α {\displaystyle \alpha } is a root of x 3 + x 2 + 1 = 0 {\displaystyle x^{3}+x^{2}+1=0}, and the powers of α {\displaystyle \alpha } are placed in counterclockwise order:

If one draws an edge x → x + c {\displaystyle x\to x+c} instead of x → x + 1 {\displaystyle x\to x+1} for every x {\displaystyle x} in G F ( q ) {\displaystyle \mathrm {GF} (q)}, where c {\displaystyle c} is any fixed element, one obtains a graph G α ( q ; c ) {\displaystyle G_{\alpha }(q;c)}. The standard graph corresponds to c = 1 {\displaystyle c=1}. The graph G α ( q ; 0 ) {\displaystyle G_{\alpha }(q;0)} consists of q {\displaystyle q} self-loops. For any c ≠ 0 {\displaystyle c\neq 0}, the graph G α ( q ; c ) {\displaystyle G_{\alpha }(q;c)} appears identical to G α ( q ) {\displaystyle G_{\alpha }(q)}, except that all edges are rotated by log α ⁡ ( c ) q − 1 × 360 ∘ {\displaystyle {\frac {\log _{\alpha }(c)}{q-1}}\times 360^{\circ }} around the center node.

Here is G α ( 8 ; α 2 ) {\displaystyle G_{\alpha }(8;\alpha ^{2})}, which differs from G α ( 8 ) {\displaystyle G_{\alpha }(8)} by a rotation of 2 7 × 360 ∘ {\displaystyle {\frac {2}{7}}\times 360^{\circ }}:

Each graph G α ( q ; c ) {\displaystyle G_{\alpha }(q;c)} visualizes the permutation σ c ( x ) = x + c {\displaystyle \sigma _{c}(x)=x+c}. The set of these q {\displaystyle q} permutations { σ c ∣ c ∈ G F ( q ) } {\displaystyle \{\sigma _{c}\mid c\in \mathrm {GF} (q)\}} forms an Elementary abelian group of order q {\displaystyle q} (isomorphic to the additive group of the field). The rotational symmetry of the graphs G α ( q ; c ) {\displaystyle G_{\alpha }(q;c)} for c ≠ 0 {\displaystyle c\neq 0} elegantly captures the algebraic indistinguishability of the non-zero elements in an elementary abelian group.

If α {\displaystyle \alpha } and β {\displaystyle \beta } are both primitive elements of G F ( q ) {\displaystyle \mathrm {GF} (q)}, then the graphs G α ( q ) {\displaystyle G_{\alpha }(q)} and G β ( q ) {\displaystyle G_{\beta }(q)} are identical if and only if α {\displaystyle \alpha } and β {\displaystyle \beta } are roots of the same primitive polynomial in G F ( p ) [ X ] {\displaystyle \mathrm {GF} (p)[X]}. Therefore, the number of distinct graphs G α ( q ) {\displaystyle G_{\alpha }(q)} equals ϕ ( q − 1 ) n {\displaystyle {\frac {\phi (q-1)}{n}}}, where ϕ {\displaystyle \phi } is Euler's totient function. Equivalently, there exist ϕ ( q − 1 ) n {\displaystyle {\frac {\phi (q-1)}{n}}} distinct Zech logarithm tables for a given field size.

If α {\displaystyle \alpha } and β {\displaystyle \beta } are multiplicative inverses of each other, then G α ( q ) {\displaystyle G_{\alpha }(q)} and G β ( q ) {\displaystyle G_{\beta }(q)} are reflections of each other.

When q {\displaystyle q} is odd, G α ( q ) {\displaystyle G_{\alpha }(q)} contains a "diagonal" edge that connects the node − 1 / 2 {\displaystyle -1/2} to 1 / 2 {\displaystyle 1/2} (where 2 − 1 {\displaystyle 2^{-1}} denotes the multiplicative inverse of 1 + 1 {\displaystyle 1+1}).

Here are the graphs G α ( q ) {\displaystyle G_{\alpha }(q)} for all q {\displaystyle q} such that the graph remains invariant (up to reflection) across all primitive elements α {\displaystyle \alpha }:

Zech's logarithm

Definition

Uses

Examples

Visualization

See also

Further reading