From: Sander Land <sander.land@...>
Date: 2008-04-16T23:49:52+09:00
Subject: Re: Primes in P?

>  Well, you could use the Miller-Rabin prime test for a speed up! See:
>
>  http://snippets.dzone.com/posts/show/4636
>
>  You may check the outcome with primegen, http://cr.yp.to/primegen.html
>
>  time -p primes 123456543211 123456543211   # done in well under a second
>
>  Cheers,
>  j. k.
>
Yes, try Miller-Rabin or some other test like it. They're not
absolutely perfect but very fast and usually good enough.

The original AKS is like O(d^12)  , where d is the number of digits of
n. It is more of a theoretical result than a practical algorithm.
Simply testing all numbers up to sqrt(n) is 2^(d/2), which is faster
for numbers up to about 200 digits (at which they both already take
far too long, of course).