{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiglesyhhto5rth2pbxwupp5xvmjcgx7ctmwas5zfslm3w6aatu5by",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpo3j5f22h32"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2607.00313v1",
  "publishedAt": "2026-07-02T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Mark Giesbrecht",
    "Armin Jamshidpey",
    "Éric Schost"
  ],
  "textContent": "**Authors:** Mark Giesbrecht, Armin Jamshidpey, Éric Schost\n\nLet $\\mathsf{E}=\\mathbb F_q[x]/(Γ)$ be an algebraic extension of degree $n$ over the finite field $\\mathbb F_q$, given by a $Γ\\in\\mathbb F_q[x]$ monic and irreducible. It is classical that any such $\\mathsf{E}$ contains an element $β\\in\\mathsf{E}$ that is normal over $\\mathbb F_q$, i.e., the conjugates $β,β^q,\\ldots,β^{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_ε((n^2\\log q)^{1+ε})+O\\,\\tilde{}\\,(n\\log^2 q)$ bit operations, for any $ε>0$. The algorithm works by showing that, for a parameter $t\\in\\mathbb F_q$, the element $β_t=(θ-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 $β_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_ε((nm\\log q)^{1+ε})$ 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.",
  "title": "Fast Deterministic Normal Bases and Circulant Polynomial Determinants"
}