The Frobenius Carousel: Normal Bases Without Guesswork ✛ ✎

Apply power, and the Frobenius carousel springs to life: each element of the finite field morphs into its q-th descendant, while the coordinates slide around the ring. This action — the Frobenius automorphism — was described by Gauss in his arithmetical investigations, but for a long time, getting the carousel to rotate smoothly without grinding to a halt came only at the cost of exhaustive search or matrix manipulations.

The secret to smooth spinning lies in the seating arrangement: you need a normal basis such that the automorphism simply cycles its elements. The authors propose not to try tickets at random, but to compute right away a list of all faulty slots. For an extension of degree n, they construct a family of candidates $β_t$ = (θ − t)⁻¹ — imagine them as cabins on the platform, and almost all are suitable.

The core of the method is ultra-fast computation of the circulant matrix determinant with polynomial entries. The matrix reduces to a characteristic polynomial in an algebra with a Gröbner basis, and a cunning p-adic lift sidesteps zero denominators in Leverrier’s formulas. Thanks to triangular sets and modular composition, the entire computation takes nearly linear time in the input size — O_ϵ((n² log q)^{1+ϵ}) bit operations. For small fields, they temporarily extend the field by logarithmic multiplication, build a normal element there, and carefully descend back — and all this is deterministic.

The carousel now starts not with eyes squeezed shut, but with full knowledge of a safe starting point. This gives cryptographic protocols guaranteed resilience, and computer algebra systems — reproducibility of computations. The next step is to speed up the projection in triangular basis to truly linear time, and then the overall complexity will drop to O˜(n²). Once Gauss rotated numbers by hand; today the algorithmic carousel does it in milliseconds, leaving us merely to admire the pure mathematics.