Elliptic curve primality
New to topics? Read the documentation here!
Polynomial time for most inputs, but not for some very rare ones. TODO can they be determined?
But it is better in practice than the AKS primality test, which is always polynomial time.