🚀 go-pugleaf

           Department of Computer Science, University of Toronto
         (SF = Sandford Fleming Building, 10 King's College Road)

       -------------------------------------------------------------

                                  THEORY
              SF1105, at 3:00 p.m., Thursday 26 November 1992

                                Shuhong Gao
                          University of Waterloo

                         " Optimal Normal Bases "

    The concept of optimal normal bases was introduced by Mullin,
Onyszchuk, Vanstone and Wilson in an attemp to efficiently implement finite
field arithmetic in hardware or software. Let F_q be a finite field of q
elements and n a positive integer. A basis N = (a_0, a_1, ... ,a_n) for
F_q^n over F_q is called a normal basis if a_i= a^{q^i} for some a in
F_q^n. For a normal basis N, it is easy to see that the n  expressions a_0
* a_i represented in the basis N itself have at least 2n-1 nonzero terms.
If there are exactly 2n-1 nonzero terms then N is called optimal.
    Mullin et al constructed two families of optimal normal bases and,
based oncomputer search results,conjectured that they are essentially all
the optimal normal bases in finite fields. In this talk I will show how all
the optimal normal bases can be determined, thus confirming their
conjecture.
    Joint work with Henrik W. Lenstra, Jr.