STILL UNDER CONSTRUCTION

The Line Problem for Cubic Extensions

Background

In [Coh2009] and [Coh2010], Stephen Cohen investigates what he calls the line problem: Given a finite field F = 𝔽_q and an extension K = 𝔽_qⁿ, and suppose that γ generates K over F (i.e., K = F(γ)); is it the case that for every non-zero β in K there exists an α in F such that β(γ + α) is primitive? Or rather, for which values of q does such a primitive element exist for every appropriate pair (β, γ)?

Cohen was able to resolve this question fully for the case of quadratic extensions. For cubic extensions, he was able to resolve it for all but 149 values of q, the largest of which was q = 9811. In [CTSB], improved sieving methods are described that reduce the number of unresolved cases considerably, with the largest remaining case being q = 4951. These cases were all checked with the program described on this page, and the result is the expected one: Such primitive elements always exist except when q = 3, 4, 5, 7, 9, 11, 13, 31, or 37.

The program used to do the final verifications, L3check, was of necessity highly optimised. This page endeavours to explain its workings, and how to use it to verify these claims.

Downloads

• L3check.cC source for the checking program
• L3.mMagma code to generate the argument list to L3check

Usage

Arguments

Basic invocation: L3check p n f0 … fn 3 lg0 … lg3 k p1 … pk

The above basic invocation runs L3check for q = pⁿ. A more detailed explanation of the arguments is provided below, but the easiest option is simply to run the provided Magma code in L3.m to generate the argument list. A typical example for q = 7:

The output will print the value of q tested, and either SUCCESS if all (β, γ) pairs were good, or FAIL and a bad pair (β, γ).

The remaining arguments are explained as follows:

• The first two arguments are the prime p and integer n such that q = pⁿ.

  In the above example, the associated arguments are 7 1, corresponding to p = 7 and n = 1 and thus q = 7¹ = 7.

• The f_i are the coefficients (in [0, p - 1]) of a monic polynomial f that defines 𝔽_q as a primitive extension of 𝔽_p. i.e., 𝔽_q = 𝔽_p[x]/f where f = f_nxⁿ + f_n-1x^n-1 … f₁x + f₀ with f_n = 1, f is irreducible over 𝔽_p, and such that any root ζ of f is a primitive element of 𝔽_q.

  Note that when q is prime this polynomial must still be chosen so as to give a primitive element of 𝔽_q = 𝔽_p. For instance, if q = 7, we cannot use f = x + 6 or f = x + 5 (since neither 1 nor 2 is primitive in 𝔽₇), but f = x + 4 is acceptable since 3 is primitive in 𝔽₇.

  In the above example, the coefficients are 4 1, corresponding to the polynomial x + 4. Since ζ is a root of this polynomial, we thus have ζ = 3.

• Similarly, the lg_i represent the coefficients of a monic cubic polynomial that defines 𝔽_q³ as a primitive cubic extension of 𝔽_q. i.e., 𝔽_q³ = 𝔽_q[t]/g where g = g₃t³ + g₂t² + g₁t + g₀ with g₃ = 1, g is irreducible over 𝔽_q, and such that any root ω of g is a primitive element of 𝔽_q³.

  However! The coefficients g_i are represented by their logarithms with respect to ζ, lg_i, so that g_i = ζ^lg_i. These logarithms are integers in the range [0, q - 2], with the special value q - 1 being used to represent zero. In particular, g₃ = 1 is represented by lg₃ = 0, since ζ⁰ = 1.

  In the above example, the associated arguments for the coefficients are 4 6 3 0. Note that 6 = 7 - 1 is the special value denoting zero, so g₁ = 0. For the other coefficients, we have ζ⁴ = 4, so g₀ = 4; ζ³ = 6, so g₂ = 6; and ζ⁰ = 1, so g₃ = 1. Thus these arguments define 𝔽_7³ as an extension of 𝔽₇ via the polynomial g = t³ + 6t² + 4.

• The final set of arguments give the primes dividing q³ - 1. First we have the number of such primes, then the remaining primes in ascending order.

  For the example, the arguments given are 3 2 3 19; this corresponds to the list of primes 2, 3, and 19. Indeed, we have 7³ - 1 = 342 = 2·3²·19.

Options

L3check also supports some options to change its behaviour. A brief description of these options will be given if invoking the program without arguments, or with an invalid argument list. All options must be provided before the first regular argument. The options available are:

Bibliography