Check primality of large prime by Miller-Rabin

Question

I need to check whether $7150309735704750359$ is prime. Naive methods, Sieve algorithm and AKS didn't work. So I tried Miller-Rabin. Now it says here that checking for some small set of $a$ is enough. But the data given are for numbers smaller than my number. So what do I do?

Answer 1

I don't know what you mean when you say these other methods "didn't work". Certainly AKS should work. In any event, "converse of Fermat's theorem" methods based on the factorization of n-1 succeed pretty easily. Hint: n-1 = 2*55621277*64276749127.

Answer 2

This is a small enough number (less than 2^64) that a large number of tools on the web will easily work. Things like Pari/GP, Python's numpy, Perl's Math::Prime::Util, etc. Web pages like Wolfram Alpha (use IsPrime[]), the MPU test web page, or Alpertron to name some.

No surprise AKS is taking too long. It will work, but most implementations are horrendously slow (as compared to the fast implementations, which are just glacial -- taking almost 8 seconds for this simple number).

For Miller-Rabin, see Best Known SPRP Base Sets for a list of bases that can be used. Unfortunately the Wikipedia page insists on listing the best sets from 1993, with only a small footnote pointing to results discovered later.