Fast Normal Basis Construction: From Randomized to Deterministic in 36 Years

Speaker: Prof. Mark Giesbrecht，University of Waterloo         

Title: Fast Normal Basis Construction: From Randomized to Deterministic in 36 Years

Language: English

Time & Venue: 2026.10.15   14:00-15:00   南楼N533

Abstract: A normal basis represents a finite field extension by the conjugates of a single element, making Frobenius act as a cyclic shift. I will discuss how to construct such bases efficiently, beginning with my 1990 joint work with Joachim von zur Gathen. We combined Hensel’s 1888 criterion with a lower bound for a polynomial analogue of Euler’s totient function to obtain a nearly optimal, error-free Las Vegas algorithm. Deterministic algorithms have improved since then, but their complexity has remained stubbornly tied to matrix multiplication. I will describe recent joint work with Armin Jamshidpey and Éric Schost giving a new deterministic construction that brings the cost close to the quadratic-time optimal. The main ideas combine a classical one-parameter family of elements with trace pairings to express normality as a determinant condition on a polynomial circulant matrix. We then give a nearly optimal algorithm for computing these determinants. This determinant algorithm is of independent interest and uses fast modular composition and triangular set lifting. I will also discuss related work on computing normal bases in number fields, where the structure of the Galois group plays a central role.