AKS (Agrawal-Kayal-Saxena) algorithm is the first known algorithm for primality testing that is both provably efficient (not dependent on generalized Riemann hypothesis) and deterministic. I shall present the analysis of this algorithm.

Paper: https://annals.math.princeton.edu/2004/160-2/p12