There are a number of modifications, but none of the improvements I'm aware of will get it remotely close to the speed of ECPP or APR-CL. For random 100-digit primes, the times for the fastest codes I'm aware of are:
- 246 days (estimated) AKS v6 paper
- 45 hours (estimated) AKS Bernstein + Voloch + Bornemann
- 2.6 hours AKS Bernstein theorem 4.1
- 0.042 seconds APR-CL (WraithX 1.1)
- 0.04 seconds APR-CL (Pari/GP 2.7.0)
- 0.029 seconds ECPP (ecpp-dj 1.03)
- 0.20 seconds ECPP (Primo 4.1.0 single thread)
At 500 digits, ECPP and APR-CL are in the 9-15 second range. AKS would take years, albeit we could trivially parallelize or distribute it.
I haven't seen anything that gives better improvements than Bernstein's 2003 paper while not being a complete rework such as adding randomization. The growth rate in practice comes out to $O(\log^{6.03} n)$ (there's almost certainly more than 0.03 variance in measurements, but the point is that it's very close to the ideal exponent of 6). Ricky points out that Lenstra Jr. and Pomerance are still actively publishing theoretical improvements, tightening the proven exponent.
The time taken at more than very small input sizes is almost entirely in the congruence test. There really should be very little time spent selecting the 'r' and 's' parameters, though it's possible to see it be non-trivial. For the congruence tests, Bernstein has a paper describing some of the methods that can be used to speed this up, and the implementations shown above use binary segmentation in GMP, as he suggests. You can see the implementation I used for timing at https://github.com/danaj/Math-Prime-Util-GMP/blob/master/aks.c, with various algorithms available.
There isn't any reason to use AKS in practice at any input size, given open source implementations of more efficient algorithms, not to mention Primo for use on large inputs. ECPP gives certificates as well, which is a huge advantage.
