FWIW :), This guy claims to have improved upon the efficiency of the AKS method. I don't doubt the varacity of his claim, I just can't understand enough of the paper to comment one way or the other:). I haven't succeeded in locating any implementations of the algorithm, nor even a decription that I can understand:(.