Zech logarithms

The multiplicative group \mathbb{F}_q^\times of a finite field is cyclic of order q - 1. If g is a generator, every nonzero element is a = g^k for a unique k \in [0, q - 2], its discrete logarithm, and multiplication, division and powering of elements become addition, subtraction and multiplication of logarithms modulo q - 1. Addition needs a table: Jacobi introduced, and Zech tabulated, the function Z with

now called the Zech (or Jacobi) logarithm [LN1997] [Hub1990]. The representation is attractive whenever a table of size q is affordable; fq_default uses it for q < 2^{16}, and the module fq_zech allows q < 2^{\mathtt{FLINT\_BITS}}.

Arithmetic with logarithms#

In fq_zech an element is stored as one word: its logarithm k, or q - 1 for zero (playing the role of \log 0 = \infty). Then, with all logarithms taken modulo q - 1 and the special value for zero handled separately,

• g^k g^l = g^{k + l}, (g^k)^{-1} = g^{-k}, (g^k)^e = g^{ke};
• the Frobenius map is \sigma^e(g^k) = g^{k p^e} and the p-th root is g^{k p^{d-1}};
• -1 = g^{(q-1)/2} for odd p (the unique element of order 2), and -1 = 1 = g^0 for p = 2, so negation adds (q - 1)/2 or nothing;
• for odd p, g^k is a square if and only if k is even, since the squares form the subgroup of index 2; its square roots are \pm g^{k/2}. For p = 2 every element is a square, and the square root of g^k is g^{k/2} or g^{(k + q - 1)/2} (q - 1 is odd);
• for i \ge j, g^i + g^j = g^j (1 + g^{i - j}) = g^{j + Z(i - j)}, where Z(i - j) is "infinite" (the sum is zero) when g^{i-j} = -1; subtraction is addition of g^{j + (q-1)/2}.

So every operation except table construction costs a few word operations and one memory access. When the table does not fit in the cache, the memory access dominates: for q \approx 10^6 the polynomial representation fq_nmod is already faster (see Arithmetic in finite fields).

Building the tables#

Let f be the defining polynomial and g the class of x in \mathbb{F}_p[x]/(f). To index elements by integers, write an element in the polynomial representation as \sum_{j < d} c_j g^j with c_j \in [0, p) and map it to the integer \nu(a) = \sum_j c_j p^j \in [0, q), its coefficients read as digits in base p. This is a bijection between \mathbb{F}_q and [0, q), with \nu(0) = 0 and \nu(1) = 1.

The tables take q words for Z, q for E and p for L; the temporary table T takes another q words. Because the construction fails for a non-primitive f, it doubles as a primitivity test: fq_zech_ctx_init_fq_nmod_ctx_check returns 0 in that case. Conway polynomials are primitive by definition, and other fq_zech contexts are created with random primitive polynomials (Defining polynomials).

Conversions, norm and trace#

The table E gives the polynomial representation of g^k directly: its coefficients are the base-p digits of E[k], which is how fq_zech_get_fq_nmod and the polynomial multiplication of fq_zech_poly convert elements. Conversely, \sum_j c_j g^j is computed as a sum of the terms g^{L[c_j] + j} with d - 1 Zech additions.

The norm of g is N(g) = \prod_{i < d} g^{p^i} = g^{(q-1)/(p-1)}, and it is (-1)^d f(0) for the monic minimal polynomial f of g; it is a generator of \mathbb{F}_p^\times, since g^{(q-1)/(p-1)} has order p - 1. The context stores it (prime_root), and then:

• N(g^k) = N(g)^k, one exponentiation modulo p (fq_zech_norm);
• the elements of \mathbb{F}_p^\times are the powers g^{m(q-1)/(p-1)} = N(g)^m, so an element of the prime field with logarithm l corresponds to the integer N(g)^{l (p-1)/(q-1)} \bmod p; fq_zech_trace sums the d conjugates g^{k p^i} with Zech additions and converts the result in this way.

Use in FLINT#

• The tables are built by fq_zech_ctx_init_fq_nmod_ctx_check, which is called by all fq_zech_ctx_init functions and by fq_default when it chooses the Zech representation.
• fq_zech_add, fq_zech_sub, fq_zech_neg, fq_zech_mul, fq_zech_inv, fq_zech_pow, fq_zech_frobenius, fq_zech_pth_root, fq_zech_sqrt, fq_zech_is_square, fq_zech_norm and fq_zech_trace implement the formulas above.
• The generic gr context of fq_zech has a dot product working directly with logarithms, used by the classical polynomial multiplication of fq_zech_poly (through _gr_poly_mullow_classical); long polynomial products convert to the polynomial representation (Multiplying polynomials over finite fields).