Talk:Miller–Rabin primality test

Python

This task can also be handled by the NZMATH modules prime and arith1 to enable its millerRabin function.--Billymac00 02:32, 3 January 2011 (UTC)

Testing Composite Probability

In addition to finding primes it is interesting to determine how often the algorithm returns composites as prime, see here. Using Ruby's miller_rabin_prime? as follows:

<lang ruby> v = (1..times).find_all { |i| miller_rabin_prime?(n,g)} puts v.length </lang>

with n=703 (19 * 37) and g=1 for times=10,000 returned 2242 false trues, which compares well with the 2286 which may be expected from. Increasing g to 5 reduced the number of false trues to 7. Increasing g to 10 reduced the number of false trues to 0 even when times was increased to 100000. Increasing times to 1000000 only returned 1 false true.--Nigel Galloway 13:47, 30 December 2012 (UTC)