Deterministically checking whether a large number is prime or composite?

Question

I'm searching for an algorithm to primality test large (like 10²⁰⁰) numbers. Are there any good algorithms?

Ideally, I'd prefer an algorithm that isn't probabalistic.

Note: Numbers have over 50 and less then 200 digits.

Answer 1

If you're looking for a non-probabalistic test, you may want to check out the AKS primality testing algorithm, which runs in roughly O(log⁶ n) time. For the number of digits you have, this is probably feasible.

That said, probabalistic primality tests are extremely good and many have exponentially small error rates. I would suggest using one of those unless there's a good reason not to.

EDIT: I just found this page containing several C++ implementations of AKS. I have no idea whether they work correctly or not, but they might be a good starting point.

Hope this helps!

Answer 2

Typically we would use a probable prime test. I recommend BPSW, which you can follow by a Frobenius test and/or some random-base Miller-Rabin tests if you want more certainty. This will be fast and arguably more certain than running some proof implementations.

Assume you say that isn't good enough. Then you really want to use ECPP and get a certificate. Reasonable implementations are Primo or ecpp-dj. These can prove primality of 200 digit numbers in well under a second, and return a certificate that can be independently verified.

APR-CL is another reasonable method. The downside is that it doesn't return a certificate so you're trusting the implementation -- you get a "yes" or "no" output that is deterministically correct if the implementation was correct. Pari/GP uses APR-CL with its isprime command, and David Cleaver has an excellent open source implementation: mpz_aprcl. Those implementations have had some code review and daily use in various software so should be good.

AKS is a horrible method to use in practice. It doesn't return a certificate, and it's not too hard to find broken implementations, which completely defeats the point of using a proof method vs. good probable prime tests in the first place. It's also horrendously slow. 200 digit numbers are well past the practical point for any implementation I'm aware of. There is a "fast" one included in the previously mentioned ecpp-dj software so you can try it out, and there are quite a few other implementations to be found.

For some idea of speed, here are times of some implementations. I don't know of any implementations of AKS, APR-CL, or BPSW that are faster than the ones shown (please comment if you know of one). Primo starts off a bit slower than ecpp-dj shown, but at 500 or so digits it is faster, and has a better slope past that. It is the program of choice for large inputs (2,000-30,000 digits).