Talk:Miller–Rabin primality test

C#

The code for method RabinMiller.IsPrime(int n, int k) returns incorrect results. For example, RabinMiller.IsPrime(181, 10) returns false even though 181 is prime. I believe the incorrect value is returned because the line

<lang C#> int mod = (int)Math.Pow(a, (double)temp) % n; </lang>

overflows.

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. Obviously these results will vary for each trial.--Nigel Galloway 13:47, 30 December 2012 (UTC)