Pith. sign in

REVIEW 1 major objections 1 minor 33 references

A deterministic algorithm finds a normal element in any finite field extension of degree n over F_q using O_ε((n² log q)^{1+ε}) + Õ(n log² q) bit operations.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-07-02 00:47 UTC pith:VYLTNSAV

load-bearing objection The paper delivers a deterministic near-quadratic algorithm for normal bases by bounding bad parameters with an explicit circulant determinant construction and a new fast circulant det routine. the 1 major comments →

arxiv 2607.00313 v1 pith:VYLTNSAV submitted 2026-07-01 cs.SC cs.CC

Fast Deterministic Normal Bases and Circulant Polynomial Determinants

Mark Giesbrecht , Armin Jamshidpey , \'Eric Schost This is my paper
classification cs.SC cs.CC
keywords normal basesfinite fieldsdeterministic algorithmscirculant matricesMoore matricespolynomial determinantsalgebraic extensions
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a deterministic procedure that, given an irreducible monic polynomial of degree n over F_q, produces an element β whose conjugates form a basis of the extension. It proves that β_t = (θ - t)^{-1} is normal for every t in F_q except at most n(n-1) exceptional values. The proof constructs a cleared Moore circulant matrix whose determinant is a polynomial of degree at most n(n-1) that vanishes exactly on those exceptions. A separate algorithm computes the determinant of any n-by-n circulant matrix whose entries are polynomials of degree at most m over F_q in O_ε((n m log q)^{1+ε}) bit operations, which is then used to locate a good t. The overall procedure therefore runs in the stated time bound for arbitrary field sizes.

Core claim

Given an irreducible monic Γ of degree n over F_q defining E = F_q[x]/(Γ), the algorithm shows that the element β_t = (θ - t)^{-1} fails to be normal for at most n(n-1) values of t; this is certified by the vanishing of the determinant of a cleared Moore circulant matrix of degree at most n(n-1) over F_{q^n}[T], equivalently realized as a trace Gram circulant matrix over F_q[T]. The determinant is computed via a fast circulant-determinant routine based on triangular-set projection and modular composition, after which a single good t is selected and the corresponding β_t is returned.

What carries the argument

The cleared Moore circulant matrix over F_{q^n}[T] (or its trace-Gram equivalent over F_q[T]), whose determinant is a univariate polynomial of degree ≤ n(n-1) that vanishes precisely when the associated β_t is not normal.

Load-bearing premise

The cleared Moore circulant matrix over F_{q^n}[T] has determinant of degree at most n(n-1) that vanishes exactly at the non-normal values of t.

What would settle it

For any small concrete pair (n,q) with n(n-1) < q, compute the determinant polynomial explicitly, extract its roots in F_q, and verify by direct linear-algebra check that β_t is normal precisely when the determinant is nonzero at t.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The algorithm is correct and runs in the stated bit complexity for every irreducible input polynomial and every prime-power q.
  • The circulant-determinant subroutine alone costs O_ε((n m log q)^{1+ε}) bit operations on an n-by-n matrix with polynomial entries of degree ≤ m.
  • When q < n(n-1) the method embeds the base field into a low-degree extension at only polylogarithmic extra cost and still returns a normal element over the original field.
  • The same matrix-construction technique supplies an explicit polynomial whose roots mark all bad parameters t.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The circulant-determinant method may extend to other resultant or characteristic-polynomial computations that arise when searching for elements with prescribed linear-independence properties.
  • If the degree bound n(n-1) on the exceptional set can be lowered by a tighter analysis of the Moore matrix, the same algorithmic skeleton would immediately yield a smaller search space or lower output polynomial degree.
  • The reduction from normality testing to a single univariate determinant evaluation suggests analogous reductions for related basis-construction problems such as primitive or free elements.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 1 minor

Summary. The paper claims a deterministic algorithm to find a normal element β in F_{q^n}/F_q with bit complexity O_ε((n² log q)^{1+ε}) + Õ(n log² q). It constructs β_t = (θ - t)^{-1} for t ∈ F_q and proves that this is normal except for ≤ n(n-1) exceptional t, by exhibiting a cleared Moore circulant matrix M(T) over F_{q^n}[T] whose determinant has degree ≤ n(n-1) and vanishes at t precisely when β_t is not normal; this is reduced to an equivalent trace Gram circulant over F_q[T]. A new deterministic near-linear-time algorithm for the determinant of an n×n circulant matrix with polynomial entries of degree ≤ m is given, achieving O_ε((nm log q)^{1+ε}) bit operations via triangular-set projection and modular composition; the small-field case is handled by embedding.

Significance. If the algebraic claims on the determinant degree and vanishing set hold, the result supplies the first deterministic algorithm for normal-basis construction whose complexity is near-optimal (matching the output size up to n^ε factors) and improves substantially on prior randomized or super-quadratic methods. The circulant-polynomial determinant routine is of independent interest for fast linear algebra over polynomial rings.

major comments (1)
  1. [Abstract] Abstract (paragraph beginning 'This is established by constructing...'): the central claim that the cleared Moore circulant matrix over F_{q^n}[T] has det of degree ≤ n(n-1) and vanishes exactly on the non-normal t ∈ F_q is load-bearing for both correctness and the stated complexity; the manuscript must supply an explicit verification that the degree bound is not exceeded by the clearing construction and that no extraneous roots appear in F_q.
minor comments (1)
  1. The notation for the parameter T versus t should be made uniform throughout to avoid confusion between the indeterminate and the evaluation point.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for explicit verification of the central algebraic claim. We address the comment below and will strengthen the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph beginning 'This is established by constructing...'): the central claim that the cleared Moore circulant matrix over F_{q^n}[T] has det of degree ≤ n(n-1) and vanishes exactly on the non-normal t ∈ F_q is load-bearing for both correctness and the stated complexity; the manuscript must supply an explicit verification that the degree bound is not exceeded by the clearing construction and that no extraneous roots appear in F_q.

    Authors: We agree that an explicit, self-contained verification strengthens the paper. In the revision we will insert a dedicated lemma immediately after the definition of the cleared Moore circulant. The lemma will (i) exhibit the precise clearing multiplier (a monic polynomial in T of degree at most n-1 arising from the denominators of the inverse entries) and show that, after multiplication, every entry remains a polynomial of degree ≤ n-1, so the determinant is of degree ≤ n(n-1); (ii) prove that any root t ∈ F_q of this determinant produces a linear dependence among the conjugates of β_t by direct expansion of the Moore matrix; and (iii) show the converse—that linear dependence implies vanishing—by reversing the same identities, establishing that no extraneous roots are introduced over F_q. The same argument will be carried through for the equivalent trace-Gram circulant over F_q[T]. These steps rely only on the standard properties of Moore matrices and the trace pairing; they do not alter the complexity analysis. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation rests on explicit algebraic constructions and independent determinant algorithm.

full rationale

The paper establishes the key degree bound deg(det) ≤ n(n-1) and the exact vanishing equivalence by constructing the cleared Moore circulant matrix over F_{q^n}[T] and replacing it with the trace Gram circulant over F_q[T]. These steps are presented as direct consequences of the matrix definitions and properties of the Moore matrix and trace, with no reduction to fitted parameters, self-definitions, or load-bearing self-citations. The fast circulant determinant routine is given a separate complexity analysis O_ε((nm log q)^{1+ε}) that does not presuppose the normal-basis count. The overall algorithm complexity follows from bounding the number of exceptional t by this degree and searching deterministically. No enumerated circularity pattern applies; the central claims remain independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on classical facts about the existence of normal bases and properties of Moore matrices in finite fields; no free parameters or new entities are introduced in the abstract.

axioms (2)
  • standard math Every finite extension of a finite field admits a normal basis (classical theorem).
    Invoked at the start of the abstract as the existence result the algorithm realizes constructively.
  • standard math The conjugates under the Frobenius generate the extension and the Moore matrix encodes linear independence over the base field.
    Used to link the determinant non-vanishing condition to normality.

pith-pipeline@v0.9.1-grok · 5928 in / 1483 out tokens · 30465 ms · 2026-07-02T00:47:44.537954+00:00 · methodology

0 comments
read the original abstract

Let $\mathsf{E}=\mathbb F_q[x]/(\Gamma)$ be an algebraic extension of degree $n$ over the finite field $\mathbb F_q$, given by a $\Gamma\in\mathbb F_q[x]$ monic and irreducible. It is classical that any such $\mathsf{E}$ contains an element $\beta\in\mathsf{E}$ that is normal over $\mathbb F_q$, i.e., the conjugates $\beta,\beta^q,\ldots,\beta^{q^{n-1}}$ form an $\mathbb F_q$-basis of $\mathsf{E}$. In this paper we give a deterministic algorithm which finds such a normal element using $O_\epsilon((n^2\log q)^{1+\epsilon})+O\,\tilde{}\,(n\log^2 q)$ bit operations, for any $\epsilon>0$. The algorithm works by showing that, for a parameter $t\in\mathbb F_q$, the element $\beta_t=(\theta-t)^{-1}$ is normal except for at most $n(n-1)$ values of $t$. This is established by constructing a "cleared Moore" circulant matrix over $\mathbb F_{q^n}[\mathcal T]$, whose determinant degree at most $n(n-1)$, such that $\beta_t$ is normal if and only the determinant is non-zero at $t\in\mathbb F_q$. For faster computation over the base field, we replace this by an equivalent trace Gram circulant matrix over $\mathbb F_q[\mathcal T]$. A main algorithmic contribution is a fast determinant algorithm for circulant matrices of polynomials, which uses triangular set projection and modular composition techniques to achieve a near-linear cost. Given an $n\times n$ circulant matrix over $\mathbb F_q[t]$ whose entries have degree at most $m>0$, we show how to compute its determinant deterministically with $O_\epsilon((nm\log q)^{1+\epsilon})$ bit operations. We complete the solution by showing how to extend this to finite fields of size less than $n(n-1)$, through an embedding in a low-degree extension field, at poly-logarithmic additional cost.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

33 extracted references · 1 canonical work pages

  1. [1]

    Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =

    Josh Alman and Ran Duan and Virginia Vassilevska Williams and Yinzhan Xu and Zixuan Xu and Renfei Zhou , title =. Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA) , year =

    2025

  2. [2]

    2013 , note =

    Emil Artin , title =. 2013 , note =

    2013

  3. [3]

    1944 , series =

    Emil Artin , title =. 1944 , series =

    1944

  4. [4]

    Proceedings of

    Daniel Augot and Paul Camion , title =. Proceedings of. 1994 , note =

    1994

  5. [5]

    , title =

    Bach, Eric and Driscoll, James and Shallit, Jeffrey O. , title =. Journal of Algorithms , volume =. 1993 , doi =

    1993

  6. [6]

    Bostan, Alin and Gonz. From. Proceedings of the Eighth International Symposium on Effective Methods in Algebraic Geometry (. 2005 , url =

    2005

  7. [7]

    1990 , doi =

    Constructing Normal Bases in Finite Fields , journal =. 1990 , doi =

    1990

  8. [8]

    Computational Complexity , volume =

    Computing. Computational Complexity , volume =. 1992 , doi =

    1992

  9. [9]

    1993 , url =

    Shuhong Gao , title =. 1993 , url =

    1993

  10. [10]

    Duke Mathematical Journal , volume =

    Perlis, Sam , title =. Duke Mathematical Journal , volume =. 1942 , doi =

    1942

  11. [11]

    Computing isomorphisms and embeddings of finite fields , journal =

    Ludovic Brieulle and Luca. Computing isomorphisms and embeddings of finite fields , journal =. 2019 , doi =

    2019

  12. [12]

    Quadratic-Time Algorithms for Normal Elements , booktitle =

    Giesbrecht, Mark and Jamshidpey, Armin and Schost,. Quadratic-Time Algorithms for Normal Elements , booktitle =. 2019 , doi =

    2019

  13. [13]

    Subquadratic-Time Algorithms for Normal Bases , journal =

    Giesbrecht, Mark and Jamshidpey, Armin and Schost,. Subquadratic-Time Algorithms for Normal Bases , journal =. 2021 , doi =

    2021

  14. [14]

    Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation , series =

    Giorgi, Pascal and Jeannerod, Claude-Pierre and Villard, Gilles , title =. Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation , series =. 2003 , doi =

    2003

  15. [15]

    2020 , doi =

    Dirk Hachenberger and Dieter Jungnickel , title =. 2020 , doi =

    2020

  16. [16]

    Mathematics of Computation , volume =

    Kaltofen, Erich and Shoup, Victor , title =. Mathematics of Computation , volume =. 1998 , doi =

    1998

  17. [17]

    and Umans, Christopher , title =

    Kedlaya, Kiran S. and Umans, Christopher , title =. SIAM Journal on Computing , volume =. 2011 , doi =

    2011

  18. [18]

    Theoretical Computer Science , volume =

    Keller-Gehrig, Walter , title =. Theoretical Computer Science , volume =. 1985 , doi =

    1985

  19. [19]

    , title =

    Lenstra, Jr., Hendrik W. , title =. Mathematics of Computation , volume =. 1991 , doi =

    1991

  20. [20]

    1997 , doi =

    Lidl, Rudolf and Niederreiter, Harald , title =. 1997 , doi =

    1997

  21. [21]

    On a Little but Useful Algorithm , booktitle =

    L. On a Little but Useful Algorithm , booktitle =. 1986 , doi =

    1986

  22. [22]

    Bulletin of the American Mathematical Society , volume =

    Moore, Eliakim Hastings , title =. Bulletin of the American Mathematical Society , volume =. 1896 , doi =

  23. [23]

    Computing

    Neiger, Vincent and Pernet, Cl. Computing. Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation , series =. 2024 , doi =

    2024

  24. [24]

    Journal of Symbolic Computation , volume =

    Poli, Alain , title =. Journal of Symbolic Computation , volume =. 1995 , doi =

    1995

  25. [25]

    Modular Composition Modulo Triangular Sets and Applications , journal =

    Poteaux, Adrien and Schost,. Modular Composition Modulo Triangular Sets and Applications , journal =. 2013 , doi =

    2013

  26. [26]

    Mathematics of Computation , volume =

    Shoup, Victor , title =. Mathematics of Computation , volume =. 1990 , doi =

    1990

  27. [27]

    Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation , series =

    Villard, Gilles , title =. Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation , series =. 2018 , doi =

    2018

  28. [28]

    Faster Modular Composition Using Two Relation Matrices , year =

    Neiger, Vincent and Salvy, Bruno and Schost,. Faster Modular Composition Using Two Relation Matrices , year =. 2601.17422 , archivePrefix =

    work page arXiv

  29. [29]

    Modern Computer Algebra , EDITION =

  30. [30]

    and Mehrabi, E

    Lebreton, R. and Mehrabi, E. and Schost, \'E. , title =. ISSAC'13 , year =

  31. [31]

    Pascal and \'E

    C. Pascal and \'E. Schost , BOOKTITLE =

  32. [32]

    Dahan and M

    X. Dahan and M. Moreno Maza and. On the complexity of the. Transgressive Computing , Pages =

  33. [33]

    Invitation to Higher Local Fields , editor =

    Erez, Boas , title =. Invitation to Higher Local Fields , editor =. 2000 , doi =

    2000