Nobody in their right mind uses AKS for primality testing. You use Miller-Rabin with an appropriate constant number of iterations, with complexity (log n)^(2 +

Nobody in their right mind uses AKS for primality testing. You use Miller-Rabin with an appropriate constant number of iterations, with complexity (log n)^(2 + o(1)). Or if you want provability, you use some fast variant of ECPP with (log n)^(4 + o(1)) complexity.