The eventual advantage of a primality test without known exceptions

Question

The primality test of Fermat with base $2$ seems to be as secure as the computer hardware for testing numbers big enough. However, I think there are an infinite numbers of false primes using this method, while there are other, slower methods without known exceptions.

My question is, given a fast method with known counter-examples, but as confident as the hardware, and given an other slower method without known counter-examples, are there rational reasons not to use the faster method?

On my laptop with my software it takes about 15 seconds to test the 1000-digit number

1322452047027942436565037520520947332219328534926245461464451630673497399869842281605205403121495065085512112811632527835511335143219424728512404164589506314036151832865422113591262717423658819022384512524477083990175389564938342263463450659443543741045174627049626561880454213438438266752362834316227459215232361006568011619896341464230840018543432335525377307690334349212691269545357233434088109345236291702956254185235509355202112324222479305916014027930215409162415936640544515330650065471413500611311539280157202020452214083126263075154272004996221351119648014115587851997522044309027951823388335313412203455585126968301605158645201093259033861308941082461581180720659364282095712511455547044223284865258155916858624598334315118323694678424919124328665223664207840283125040006516859355687631380963074131290568442593765531248815520551332092441994428154844300406075085049654208658614492190983122308329436402869242613380509102628222319118312045540213090658245133132311523103392960535908761111443867

to be prime with Fermat base 2. It would be interesting to see comparisons with other methods.

Answer 1

No matter how good the hardware is, you won't get a result that is better than what the algorithm gives, so if you're using an algorithm that detects probable primes and you want primes, you need to do something else, so (if this was supposed to be on topic at MSe) this comes down to the algorithms.

If it's sufficiently fast to check whether a number is a known counter-example: no, but it isn't.

If the fast algorithm has infinitely many counterexamples, we can't have a list of all the counterexamples, so we're basically back to having to check whether a number that the fast algorithm says might be prime, really is prime using an exact algorithm.

Given that it can eliminate some non-primes, there might still be an advantage to running the fast algorithm first though - but is has to eliminate a significant portion of non-primes to be worth it. Some of the prime hunting distributed computing projects online does various things, like sieving out all non-primes that are multiple of known "small" (compared to the numbers they want to check) primes.

Answer 2

For many people, using a good method such as BPSW (not a single Fermat test), is good enough. More importantly, the code for such a test is much simpler than good proof software, so in many cases it has more trust.

A few example times with your number to give some idea. Your times will vary depending on software and computer. This is C+GMP. PFGW isn't much different than the GMP Fermat speed at this size (it starts getting faster over 2000 digits).

 9 ms  Fermat base 2
 9 ms  Miller-Rabin base 2
90 ms  Miller-Rabin 10 random bases
28 ms  BPSW (Miller-Rabin base 2 plus extra-strong Lucas)
29 ms  Frobenius(2,P)
21 ms  Frobenius-Underwood
35 ms  Frobenius-Khashin

There are no known counterexamples to even crippled versions of BPSW, it's been around for 36 years, and is the main method used in many (most?) math packages. A number that passes BPSW and a Frobenius and/or a few random-base Miller-Rabin tests satisfies me. But it's still a probable prime. To some extent it depends where the proof came from. Is it a Primo certificate? A run of Pari/GP APR-CL? Some random proof software a student wrote? An assertion found on an internet page? The latter two IMO have much more chance of error than good probable prime tests, without even having to bring up hardware.

One big advantage of ECPP over the above (or other methods like APR-CL or AKS) is that it can generate a certificate. This lets other people relatively quickly verify that the number really is a definite prime, rather than just taking someone's word for it.

0 min 31 sec   Primo 4.2.0 with 8 threads
3 min  7 sec   Pari/GP 2.8.0 APR-CL
4 min 58 sec   ECPP-DJ
> 25 years     AKS (Bernstein 4.1)

Using the standard AKS V6 algorithm would take over 32GB and millions of years to finish. It is, however, trivially parallelized.