5 ms·
Don't forget AKS, which is deterministic and faster than trial division. Can be a bit of a pain to implement though.
by traldan 15y ago
Don't forget AKS, which is deterministic and faster than trial division. Can be a bit of a pain to implement though.
- mappu 15y agoAnother 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 http://plan.dpk.org.uk seem to be broken so i'm not sure if this has bigints.
- dpkendal 15y agoPlan isn't done yet. You can see the preliminary Ruby implementation at http://github.com/dpkendal/Plan 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 15y agoHaving 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.
- evandijk70 15y agoElliptic Curve Primality Proving is way faster in practice, and although it's running time is not deterministic, it does give a proof that a number is prime.