[mappu]

Another vote for AKS. Our cryptography lecturer skimmed over the Fermat and Miller-Rabin tests, then just said "AKS is better" and left it at that.. I believe the best approach is to do a few iterations of a non-deterministic test to quickly rule out some numbers and then start on a deterministic one. Wikipedia's description of the algorithm still looks pretty simple and being deterministic makes me feel all warm and fuzzy inside.

The documentation and download links for Plan at http://plan.dpk.org.uk seem to be broken so i'm not sure if this has bigints.

[dpkendal]

Plan isn't done yet. You can see the preliminary Ruby implementation at http://github.com/dpkendal/Plan, but I'm now working on a "final" version in RPython to be compiled by PyPy. The download and docs links are there to show what the website will look like eventually.

It should have bigints, though.

[traldan]

Having implemented AKS in Python and Sage, it can get pretty slow - obviously, nowhere near a good probabilistic test even to a staggering degree of certainty. That said, most of the algorithm is very quick. It might be smart to run its basic compositeness tests, do a pseudoprime test, and only do the polynomial mod operation if the number passes.