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 two arguments. One is an odd integer, the other 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. User:bengt

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)

It is not the absence on the task page of a function name or that the only function with the mentioned parameter names (n and k) is not doing the algorithm that is my problem, although both these things makes it more difficult. My problem is that I can not see any of the exported functions doing the task. Therefore I think that the Erlang solution might not be correct. User:bengt

Erlang

Miller-Rabin primality test in Erlang uses a floating point power function and truncation to restore to integer. 
This combination begins to fall short when the integer being tested is up to approximately 90,000,000. At these 
large sizes, the primes found are correct but too many correct primes are not found. The following modifications 
are helpful: an integer power function, power/2, will replace floating point power function, math:pow/2; in function
mr_series/4, math:pow/2 is replaced by power:power/2; in function pow_mod/3, the same replacement is made
and truncations are eliminated, also the expression E/2 is replaced by E div 2. One final change is to replace the
expression trunc(D/2) in find_ds/2 with the expression D div 2. By dogwood, 1/16/2014 @ 11:30pm.

-module(power).
-export([power/2]).
power(X, N) ->
   power(X, N, 1).
power(X, N, Acc) ->
   if
       N /= 0 -> power(X, N - 1, X * Acc);
       true   -> Acc
   end.

mr_series(N, A, D, S) when N rem 2 == 1 ->
   Js = lists:seq(0, S),
   lists:map(fun(J) -> pow_mod(A, power:power(2, J)*D, N) end, Js).

pow_mod(B, E, M) ->
   case E of
       0 -> 1;
       _ -> case ((E rem 2) == 0) of
                true -> (power:power(pow_mod(B, (E div 2), M), 2)) rem M;
                false -> (B*pow_mod(B, E-1, M)) rem M
            end
   end.

find_ds(D, S) ->
   case D rem 2 == 0 of
       true ->
           find_ds(D div 2, S+1);
       false ->
           {D, S}
   end.

Tcl

Is Tcl correct? It has 1 as a prime.

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)