Ciro Santilli @cirosantilli 34

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.