[drhodes]

The proof is not too bad in Lean4. I'm nothing special and I've got it down to 9 lines. But, maybe that is considered pretty tedious vs. what expectations one might have. In any case, it is an exercise in Heather MacBeth's free book: The Mechanics of Proof,

https://hrmacbeth.github.io/math2001/04_Proofs_with_Structur...

btw, that book is a lot of fun to work through.

[mathgradthrow]

The obvious proof term for isprime p is exponential compared to the size of p. The AKS proof term is polynomial, but still very bad.

[mathgradthrow]

https://en.m.wikipedia.org/wiki/Primality_certificate