For my talk I'm going to take a small deviation from graph theory and (pure) combinatorics into the realm of finite fields. Normal bases are extremely useful for applications like cryptography where exponentiation to large powers is common. In this talk, I explain how normal bases can be used in practice and outline a measure of the bottleneck of using normal bases (called the complexity of the basis). Then, I give some constructions of normal bases with low complexities, including some very recent work describing the complexities of normal bases due to so-called Gauss periods. Time permitting, I will present an algorithm for exhaustively searching for normal bases which looks at finite fields in a very combinatorial way. This talk supposes very little knowledge of finite fields and should be accessible to all. Pieces of this talk are joint with Daniel Panario, Lucia Moura and Ariane Masuda (Ottawa-Carleton) and also Theo Garefalakis and Maria Christopoulou (Crete).