Probabilistic Construction of Normal Basis

Abstract

Let GF(q) be the finite field with q elements. A normal basis polynomial f in GF(q)[x] of degree n is an irreducible polynomial, whose roots form a (normal) basis for the field extension (GF(q^n) : GF(q). We show that a normal basis polynomial of degree n can be found in expected time O(n^(2 + varepsilon) . log(q) + n^(3 + varepsilon) $, when an arithmetic operation and the generation of a random constant in the field GF(q) cost unit time.

Given some basis B = alpha_1, alpha_2,..., alpha_n for the field extension GF(qn) : GF(q) together with an algorithm for multiplying two elements in the B-representation in time O(n^beta), we can find a normal basis for this extension and express it in terms of B in expected time O(n^(1 + beta + varepsilon) € log(q) + n^(3 + varepsilon).