You're right, AKS is not a very efficient algorithm and randomized tests are generally good enough. But, there are exact tests which do run fast in practice, su

You're right, AKS is not a very efficient algorithm and randomized tests are generally good enough. But, there are exact tests which do run fast in practice, such as ECPP. Here's some of the largest primes found using ECPP: http://primes.utm.edu/top20/page.php?id=27 http://primes.utm.edu/top20/page.php?id=27 Note the largest there is 30,950 digits, which is about 102,813 bits unless I did my math wrong, so I bet it is usable for 1024-bit numbers. Non-exact methods are much much faster of course, but when you really really need exactness it is an option.