Comment by qyph

https://en.wikipedia.org/wiki/AKS_primality_test though it's number theory, and concerned with numbers of size n, rather than lists of length n.

Also relevant: https://www.cs.yale.edu/homes/aspnes/pinewiki/Derandomizatio...