You are correct. AKS (v6, Voloch, or Bernstein) is O(log^6(n)) with large constants. A nice polynomial but both large constants and a larger exponent than we'

You are correct. AKS (v6, Voloch, or Bernstein) is O(log^6(n)) with large constants. A nice polynomial but both large constants and a larger exponent than we'd like. APR-CL is O(log^K(n)) where K = C*log(log(log(n))), which means for practical purposes it's in the range 3-5, hence has a lower exponent than AKS. As n goes to infinity it does finally exceed AKS, but at that point n is so large as to not be practically computable. ECPP is conjectured O(log^5(n)) or O(log^4(n)) depending on algorithm used. Both Primo and ecpp-dj implementations show O(log^4(n)) growth though the latter doesn't scale well past 1000 digits due to a limited polynomial dictionary. Primo scales very well and has generated results for primes over 30k digits -- much larger than the others. I expect Pari/GP's ECPP implementation to eventually compete nicely when it's ready. Miller-Rabin and BPSW are both O(log^(2+c)(n)), where c is between 0 and 1 depending on the multiplication method, so exponent 2 to 3. But of course these are probabilistic. To my knowledge this has not changed recently. There haven't been substantial improvements to AKS since Bernstein's 2003 paper, which still results in an exponent of 6, though lowers the constant factors by many orders of magnitude. In 2006, Bernstein published a randomized version of AKS which runs in O(log^4(n)). So the same exponent as ECPP but also having the same "downside" of using randomization, and Bernstein notes that it was still slower than ECPP.