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.

Erlang

The task asks for a function with arguments n and k. N is an odd integer, k is a parameter (also integer?). It seems to me that there is no such function in the Erlang module. I could be wrong since the module exports all its functions making it more difficult to be sure.

I read this task as just stating that this particular algorithm is to be used, not necessarily the same variable and function names. (But that's just my guess). --Paddy3118 (talk) 05:17, 1 September 2013 (UTC)

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)