1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Short answer: this test detects probable primes, not primes. Also read en.wikipedia.org/wiki/Fermat_primality_test#Flaw. $\endgroup$ – Yves Daoust Jun 24 '16 at 8:41
  • $\begingroup$ @YvesDaoust, yes but when it comes to computers there are no totally safe computations. The risk of a false prime for a $1000$-digit number might be $1$ to $N$, where N is the number of particles in Universe... $\endgroup$ – Lehs Jun 24 '16 at 8:44
  • 1
    $\begingroup$ The false positives of that test is totally unrelated to the hardware. - And anyone seriously hunting primes using a computer always checks any finds on other computers, to minimise the effect of hardware errors. (There are other theoretical reasons - like cosmic radiation - but then it comes down to probabilities) $\endgroup$ – Henrik Jun 24 '16 at 8:47
  • 2
    $\begingroup$ @lehs: then you have more resons to worry. You can have a false prime either by algorithmic behavior or by computer mistake. :) $\endgroup$ – Yves Daoust Jun 24 '16 at 8:50
  • $\begingroup$ @Henrik: well that's a rational reason. Testing on different computers could be expected to be independent events, while testing with different bases and Fermat isn't. 1+. $\endgroup$ – Lehs Jun 24 '16 at 9:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi DanaJ and thanks for your enlightening answer. Also I noticed that the actual number takes about the same time with Miller-Rabin and with Fermat, so it isn't the perfect example. I wonder about the counter-examples. The fact that those can be constructed for some methods, make them possible to detect. But other methods without this possibility, might have as many counterexamples, but virtually impossible to find. Or? $\endgroup$ – Lehs Jun 24 '16 at 18:07
  • $\begingroup$ I haven't found Fermat to be any faster than Miller-Rabin when the same big number package is used. It makes some sense, as M-R can reject numbers with less work, but for numbers that pass ends up doing the same work. $\endgroup$ – DanaJ Jun 24 '16 at 18:35
  • $\begingroup$ Interesting, I suppose I don't understand Miller-Rabin well. Perhaps I will abandon Fermat and go back to Miller-Rabin, since I have noticed that MR is somewhat more secure. $\endgroup$ – Lehs Jun 24 '16 at 18:43
  • $\begingroup$ Deterministic probable prime tests, such as BPSW or the Frobenius tests as shown, have the possibility of fixed counterexamples. Using Miller-Rabin with the first 'n' prime bases was popular in the 90s, but Arnault in 1994 showed how to construct counterexamples, and that plus Pinch's 1993 paper were good reasons for software to stop using that method. BPSW would have the same issue, it's just much, much harder to find an example. Adding good randomness removes the fixed nature, e.g. adding a single random-base M-R test to BPSW makes the NSA's secret counterexample still often fail.. $\endgroup$ – DanaJ Jun 24 '16 at 18:44
  • $\begingroup$ The proof methods, such as BLS75, AKS, APR-CL, and ECPP, when implemented and run without error, will have no counterexamples. It is not possible for a composite to pass the test. With an ECPP certificate, one can verify that the proof is valid -- hence immune to most software and hardware mistakes, though not user errors in application (and assumes the verification process is independent). $\endgroup$ – DanaJ Jun 24 '16 at 18:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You don't have to check for counter-examples just because they exists. If the probability of the test is as confident as the hardware, why bother? $\endgroup$ – Lehs Jun 24 '16 at 8:38
  • $\begingroup$ @Lehs, if one is publishing results, or a large project is depending on the results, then "the hardware" isn't easily quantifiable. Hence things like factordb that store primality certificates. I completely agree with Henrik that even proof methods typically run pretests that include very good probable prime tests, as they can weed out almost all composites very quickly, so the (maybe relatively) time consuming proof is only done on numbers that we expect to pass. Primo used to run BPSW on the input and all intermediate numbers, ECPP-DJ does this also.. $\endgroup$ – DanaJ Jun 24 '16 at 19:03
  • $\begingroup$ @DanaJ: yes, I guess it all depends on the circumstances. I don't publish anything but often want to test conjectures. And then I rather use the fastest method before the safest. $\endgroup$ – Lehs Jun 24 '16 at 19:11
  • $\begingroup$ @Lehs, In many cases, especially when testing conjectures, using the fastest decent method first is best, then you can go back and use more stringent tests later to verify if it wasn't enough. This is quite common I believe with very large inputs (e.g. 10k, 100k, etc. digits) using PFGW since it is so much faster than anything else. $\endgroup$ – DanaJ Jun 24 '16 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.