Alice McKean's Undergraduate Thesis

Abstract

In this thesis we explore formalizing the AKS primality decision algorithm in the Agda proof assistant. We begin with a discussion of the AKS algorithm, an algorithm that determines if a given input is prime or composite. This algorithm will guide the development of basic number theory in the Agda programming language. This language is a dependently typed formal logic capable of ensuring the correctness of mathematical statements. In this mathematical assembly we prove the correctness of the exponentiation by squaring algorithm. Then we explore the nature of recursive algorithms by convincing Agda that their recursion is well founded and terminating. Lastly we provide a fully formalized brute force primality decision procedure.