On 08/23/2012 04:43 AM, Steven D'Aprano wrote: > On Wed, Aug 22, 2012 at 11:39:46PM -0400, Dave Angel wrote: >> On 08/22/2012 07:32 PM, Richard D. Moores wrote: >>> <snip> >>> >>> My code uses gmpy2.is_prime() (lines 79 and 89). is_prime() is VERY fast. >> You do know that this gmpy2 function is only statistically correct ? it >> can false positive. I don't know what the probs are, but it uses >> Miller-Rabin, with a default factor of 25. > What Dave means is: > > - If gmpy2.is_prime says a number is not prime, then that is > certainly true; > > - but if it says that a number is prime, then that is only > probably true. > > With 25 Miller-Rabin tests, the probability of a false positive is (if I > remember correctly) 1 time in 4**25 or about 1 time in a million > billion. (That's American billion, 10**9, not old-style English > billion.) If you tested a thousand prime numbers a second for thirty > thousand years, you would expect perhaps one false positive. > > The odds are much higher that a hardware fault or stray cosmic ray > hitting the CPU or memory chip will cause the computer to calculate the > wrong answer. >
I knew of the Miller Rabin test, but I did not know the probabilities involved. I'm a little surprised I didn't see any docs on the gmpy2 site that gave such probabilities. it defaults to 25, without explaining how that number relates to anything in the wikipedia article. https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Does anyone know if the gmp2 code is testing the sequence described in wikipedia, where a is 2, 3, 5, 7, 11, 13, and 17 ? If that relates directly, it would seem that 7 tests would give 100% confidence for n up to 14+ digits. -- DaveA _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor