Fast primality test with 100% certainty?

Question

I'm using GMP (with MPIR) for arbitrary size datatypes. I also use its primality test function, which uses Miller-Rabin method, but it is not accurate. This is what I want to fix.

I was able to confirm that the number 18446744073709551253 is a prime by using brute-force, with the sqrt approach.

Is there any way of checking large numbers being prime or not, with 100% accuracy?

• It should not use too much memory/storage space, few megabytes is acceptable.

• It should be faster than the sqrt method I used.

• It should work for numbers that are at least 64bit in size, or larger.

• Finally, it should be 100% accurate, no maybes!

What are my options ?

I could live with the brute force method (for 64bit numbers) though, but out of interest, I want faster & larger. Also, the 64bit number check was too slow: total 43 seconds!

Answer 1

For very large numbers, the AKS primality test is a deterministic primality test that runs in time O(log^7.5n log log n), where n is the number of interest. This is exponentially faster than the O(√n) algorithm. However, the algorithm has large constant factors, so it's not practical until your numbers get rather large.

Hope this helps!