Talk:Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (→Erlang: Needs a power function that operates using BigNums.) |
m (→Erlang) |
||
Line 18: | Line 18: | ||
== Erlang == |
== 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. |
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. |
||
-module(power). %%% Add this integer power function to use in place of math:pow/2 in the main procedure. |
|||
-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. |
|||
%%% Modify mr_series/4 to read as follows: |
|||
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). |
|||
%%% Modify pow_mod/3 to read as follows: |
|||
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. |
|||
%%% END OF NOTE |
|||
== Tcl == |
== Tcl == |