A lot of the problem is that the types of people who care about deterministic results care more about asymptotic runtime than wall clock runtime. The other prob

A lot of the problem is that the types of people who care about deterministic results care more about asymptotic runtime than wall clock runtime. The other problem is that the asymptotics of AKS are still pretty bad (log(n)^7.5 vs log(n)^2 for Miller Rabin).