Elliptic Curve Primality Proving is way faster in practice, and although it's running time is not deterministic, it does give a proof that a number is prime.