Case Van Horsen wrote the following to me about gmpy2.is_prime. I post it with his permission.
Dick Moores The summary: gmpy2.is_prime() just provides direct access to the underlying library (GMP or MPIR) function. Depending on the library and version, the behavior is subtly different. With the current version, both libraries behave similarly - the Miller-Rabin test is repeated 25 times. The sequence of bases checked are "random" values. The bases depend on the value of the number being tested. The bases really aren't random since same set of bases is used for each test of a given number. (Testing with 5 repetitions followed by another test with 10 repetitions actually repeats the tests with the first 5 bases and then tries 5 more bases. It is not the same as testing with 15 repetiions.) The Miller-Rabin test actually detects composite numbers. It will fail to detect a composite number with at most 1/4 of all possible bases. So after 5 tests, composite numbers are detected with a guaranteed error of 1 in 1024. On average, the error rate is less than that, but for certain composites the worst-case error estimates can be reached. The worst-case is reached when the number being checked is p*(2p-1) where both p and 2p-1 are prime. A few people have tried worst-case numbers with GMP and have found many values that require 10 or more iterations. (One value that requires 15 iterations has been found.) So the default of 25 iterations is reasonable but it could be set higher if you are truly paranoid however this will make the test slower for actual primes. An alternative primality test is known as the BPSW test. It is available in gmpy2 as is_bpsw_prp(). IIRC, the implementation requires about the same running time as 10 iterations of Miller-Rabin. But the biggest advantage is that there are no known false results. The test has not been proven to work 100% of the time. It is conjectured that there are false results should occur but no one has ever found one. The MPIR library has a faster version of the BPSW test but I don't make it available at the moment. I will probably add it to gmpy2 soon. _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
