Based on Agrawal et al. (n.d.), which presents a poly-time algorithm for deciding primality. Primality is in co-NP; any divisor works as a certificate for compositeness. Primality is also in NP. Saw Pratt Certificates as an example of a primality certificate. Briefly saw how fast exponentiation by squaring and checking for perfect powers works. Stated and proved the correctness and advertised time complexity of the AKS algorithm, but much of that went over my head. See Chen (2015), Pati (n.d.) for cyclotomic polynomials.
References
Agrawal, M., Kayal, N., & Saxena, N. (n.d.). PRIMES Is in P.
Chen, E. (2015). Orders Modulo A Prime. https://web.evanchen.cc/handouts/ORPR/ORPR.pdf
Pati, S. (n.d.). Cyclotomic Polynomials and Their Applications.