Probabilistic Construction of Normal Basis. (Note)
Gudmund Skovbjerg Frandsen · 1998
Let Fq be the finite field with q elements. A normal basis polynomial f ∈ Fq[x] of degree n is an irreducible polynomial, whose roots form a (normal) basis for the field extension Fqn : Fq. We show that a normal basis polynomial of degree n can be found in expected time O(n · log(q) + n), when an arithmetic operation and the generation of a random constant in the field Fq cost unit time. Given some basis B = {α1, α2, ..., αn} for the field extension Fqn : Fq together with an algorithm for multiplying two elements in the Brepresentation in time O(n), we can find a normal basis for this extension and express it in terms of B in expected time O(n · log(q) + n). CR Categories: F.2.1. 1991 Mathematics Subject Classification: Primary 11Y16; Secondary 11T30. Related Work. [BDS90] give a probabilistic construction of a normal basis for Fqn : Fq for restricted values of q and n. They use that the ground field Fq can have at most n(n− 1) elements a for which g(a) = f(a) (a− α)f ′(α) ∈ Fqn is not a normal basis element, when f is an arbitrary but fixed irreducible polynomial of degree n over Fq and α is a root of f [Art48, implicit in proof of theorem 28]. Hence, a random a ∈ Fq leads to a normal basis element g(a) ∈ Fqn with probability ≥ 12 when q > 2n(n−1). By our lemma 1 (last part) an arbitrary b ∈ Fqn is a normal basis element with probability ≥ 12 , under the same restriction. Hence, our construction may also be used in the restricted case without loss of efficiency. Deterministic constructions can be found in [BDS90, Len91]. 1This research was supported by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (project ALCOM). 2Department of Computer Science, Aarhus University, Ny Munkegade, 8000 Aarhus C, Denmark. [email protected]