Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(→{{header|C}}: adding a 64-bit deterministic version of the Miller-Rabin primality test.) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 29: | Line 29: | ||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="11l">F isProbablePrime(n, k = 10) |
||
I n < 2 | n % 2 == 0 |
I n < 2 | n % 2 == 0 |
||
R n == 2 |
R n == 2 |
||
Line 57: | Line 57: | ||
R 1B |
R 1B |
||
print((2..29).filter(x -> isProbablePrime(x)))</ |
print((2..29).filter(x -> isProbablePrime(x)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 77: | Line 77: | ||
such as for the [[Carmichael 3 strong pseudoprimes]] the [[Extensible prime generator]], and the [[Emirp primes]]. |
such as for the [[Carmichael 3 strong pseudoprimes]] the [[Extensible prime generator]], and the [[Emirp primes]]. |
||
< |
<syntaxhighlight lang="ada">generic |
||
type Number is range <>; |
type Number is range <>; |
||
package Miller_Rabin is |
package Miller_Rabin is |
||
Line 85: | Line 85: | ||
function Is_Prime (N : Number; K : Positive := 10) return Result_Type; |
function Is_Prime (N : Number; K : Positive := 10) return Result_Type; |
||
end Miller_Rabin;</ |
end Miller_Rabin;</syntaxhighlight> |
||
The implementation of that package is as follows: |
The implementation of that package is as follows: |
||
< |
<syntaxhighlight lang="ada">with Ada.Numerics.Discrete_Random; |
||
package body Miller_Rabin is |
package body Miller_Rabin is |
||
Line 143: | Line 143: | ||
end Is_Prime; |
end Is_Prime; |
||
end Miller_Rabin;</ |
end Miller_Rabin;</syntaxhighlight> |
||
Finally, the program itself: |
Finally, the program itself: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO, Miller_Rabin; |
||
procedure Mr_Tst is |
procedure Mr_Tst is |
||
Line 171: | Line 171: | ||
Ada.Text_IO.Put ("Enter the count of loops: "); Pos_IO.Get (K); |
Ada.Text_IO.Put ("Enter the count of loops: "); Pos_IO.Get (K); |
||
Ada.Text_IO.Put_Line ("What is it? " & Result_Type'Image (Is_Prime(N, K))); |
Ada.Text_IO.Put_Line ("What is it? " & Result_Type'Image (Is_Prime(N, K))); |
||
end MR_Tst;</ |
end MR_Tst;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 183: | Line 183: | ||
Using the big integer implementation from a cryptographic library [https://github.com/cforler/Ada-Crypto-Library/]. |
Using the big integer implementation from a cryptographic library [https://github.com/cforler/Ada-Crypto-Library/]. |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO, Crypto.Types.Big_Numbers, Ada.Numerics.Discrete_Random; |
||
procedure Miller_Rabin is |
procedure Miller_Rabin is |
||
Line 268: | Line 268: | ||
Ada.Text_IO.Put_Line("Prime(" & S & ")=" & Boolean'Image(Is_Prime(+S, K))); |
Ada.Text_IO.Put_Line("Prime(" & S & ")=" & Boolean'Image(Is_Prime(+S, K))); |
||
Ada.Text_IO.Put_Line("Prime(" & T & ")=" & Boolean'Image(Is_Prime(+T, K))); |
Ada.Text_IO.Put_Line("Prime(" & T & ")=" & Boolean'Image(Is_Prime(+T, K))); |
||
end Miller_Rabin;</ |
end Miller_Rabin;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 276: | Line 276: | ||
Using the built-in Miller-Rabin test from the same library: |
Using the built-in Miller-Rabin test from the same library: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO, Crypto.Types.Big_Numbers, Ada.Numerics.Discrete_Random; |
||
procedure Miller_Rabin is |
procedure Miller_Rabin is |
||
Line 301: | Line 301: | ||
Ada.Text_IO.Put_Line("Prime(" & T & ")=" |
Ada.Text_IO.Put_Line("Prime(" & T & ")=" |
||
& Boolean'Image (LN.Mod_Utils.Passed_Miller_Rabin_Test(+T, K))); |
& Boolean'Image (LN.Mod_Utils.Passed_Miller_Rabin_Test(+T, K))); |
||
end Miller_Rabin;</ |
end Miller_Rabin;</syntaxhighlight> |
||
The output is the same. |
The output is the same. |
||
Line 310: | Line 310: | ||
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}} |
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}} |
||
<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has no FORMATted transput, also it generates a call to undefined C LONG externals }} --> |
<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has no FORMATted transput, also it generates a call to undefined C LONG externals }} --> |
||
< |
<syntaxhighlight lang="algol68">MODE LINT=LONG INT; |
||
MODE LOOPINT = INT; |
MODE LOOPINT = INT; |
||
Line 347: | Line 347: | ||
print((" ",whole(i,0))) |
print((" ",whole(i,0))) |
||
FI |
FI |
||
OD</ |
OD</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 355: | Line 355: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
ahk forum: [http://www.autohotkey.com/forum/post-276712.html#276712 discussion] |
ahk forum: [http://www.autohotkey.com/forum/post-276712.html#276712 discussion] |
||
< |
<syntaxhighlight lang="autohotkey">MsgBox % MillerRabin(999983,10) ; 1 |
||
MsgBox % MillerRabin(999809,10) ; 1 |
MsgBox % MillerRabin(999809,10) ; 1 |
||
MsgBox % MillerRabin(999727,10) ; 1 |
MsgBox % MillerRabin(999727,10) ; 1 |
||
Line 395: | Line 395: | ||
y := i&1 ? mod(y*z,m) : y, z := mod(z*z,m), i >>= 1 |
y := i&1 ? mod(y*z,m) : y, z := mod(z*z,m), i >>= 1 |
||
Return y |
Return y |
||
}</ |
}</syntaxhighlight> |
||
=={{header|bc}}== |
=={{header|bc}}== |
||
Line 401: | Line 401: | ||
{{works with|OpenBSD bc}} |
{{works with|OpenBSD bc}} |
||
(A previous version worked with [[GNU bc]].) |
(A previous version worked with [[GNU bc]].) |
||
< |
<syntaxhighlight lang="bc">seed = 1 /* seed of the random number generator */ |
||
scale = 0 |
scale = 0 |
||
Line 468: | Line 468: | ||
} |
} |
||
} |
} |
||
quit</ |
quit</syntaxhighlight> |
||
=={{header|BQN}}== |
=={{header|BQN}}== |
||
Line 474: | Line 474: | ||
The function <code>IsPrime</code> in bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn] uses deterministic Miller-Rabin to test primality when trial division fails. The following function, derived from that library, selects witnesses at random. The left argument is the number of witnesses to test, with default 10. |
The function <code>IsPrime</code> in bqn-libs [https://github.com/mlochbaum/bqn-libs/blob/master/primes.bqn primes.bqn] uses deterministic Miller-Rabin to test primality when trial division fails. The following function, derived from that library, selects witnesses at random. The left argument is the number of witnesses to test, with default 10. |
||
< |
<syntaxhighlight lang="bqn">_modMul ← { n _𝕣: n|× } |
||
MillerRabin ← { 𝕊n: 10𝕊n ; iter 𝕊 n: !2|n |
MillerRabin ← { 𝕊n: 10𝕊n ; iter 𝕊 n: !2|n |
||
# n = 1 + d×2⋆s |
# n = 1 + d×2⋆s |
||
Line 493: | Line 493: | ||
C ← { 𝕊a: s MR a Pow d } # Is composite |
C ← { 𝕊a: s MR a Pow d } # Is composite |
||
{0:1; C •rand.Range⌾(-⟜2) n ? 0; 𝕊𝕩-1} iter |
{0:1; C •rand.Range⌾(-⟜2) n ? 0; 𝕊𝕩-1} iter |
||
}</ |
}</syntaxhighlight> |
||
The simple definition of <code>_modMul</code> is inaccurate when intermediate results fall outside the exact integer range (this can happen for inputs around <code>2⋆26</code>). When replaced with the definition below, <code>MillerRabin</code> remains accurate for all inputs, as floating point can't represent odd numbers outside of integer range. |
The simple definition of <code>_modMul</code> is inaccurate when intermediate results fall outside the exact integer range (this can happen for inputs around <code>2⋆26</code>). When replaced with the definition below, <code>MillerRabin</code> remains accurate for all inputs, as floating point can't represent odd numbers outside of integer range. |
||
< |
<syntaxhighlight lang="bqn"># Compute n|𝕨×𝕩 in high precision |
||
_modMul ← { n _𝕣: |
_modMul ← { n _𝕣: |
||
# Split each argument into two 26-bit numbers, with the remaining |
# Split each argument into two 26-bit numbers, with the remaining |
||
Line 506: | Line 506: | ||
Mul ← × (⊣ ⋈ -⊸(+´)) ·⥊×⌜○Split |
Mul ← × (⊣ ⋈ -⊸(+´)) ·⥊×⌜○Split |
||
((n×<⟜0)⊸+ -⟜n+⊢)´ n | Mul |
((n×<⟜0)⊸+ -⟜n+⊢)´ n | Mul |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="bqn"> MillerRabin 15485867 |
||
1 |
1 |
||
MillerRabin¨⊸/ 101+2×↕10 |
MillerRabin¨⊸/ 101+2×↕10 |
||
⟨ 101 103 107 109 113 ⟩</ |
⟨ 101 103 107 109 113 ⟩</syntaxhighlight> |
||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
{{trans|bc}} |
{{trans|bc}} |
||
< |
<syntaxhighlight lang="bracmat">( 1:?seed |
||
& ( rand |
& ( rand |
||
= |
= |
||
Line 586: | Line 586: | ||
& !primes:? [-11 ?last |
& !primes:? [-11 ?last |
||
& out$!last |
& out$!last |
||
);</ |
);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>937 941 947 953 967 971 977 983 991 997</pre> |
<pre>937 941 947 953 967 971 977 983 991 997</pre> |
||
Line 593: | Line 593: | ||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
'''miller-rabin.h''' |
'''miller-rabin.h''' |
||
< |
<syntaxhighlight lang="c">#ifndef _MILLER_RABIN_H_ |
||
#define _MILLER_RABIN_H |
#define _MILLER_RABIN_H |
||
#include <gmp.h> |
#include <gmp.h> |
||
bool miller_rabin_test(mpz_t n, int j); |
bool miller_rabin_test(mpz_t n, int j); |
||
#endif</ |
#endif</syntaxhighlight> |
||
'''miller-rabin.c''' |
'''miller-rabin.c''' |
||
{{trans|Fortran}} |
{{trans|Fortran}} |
||
For <code>decompose</code> (and header <tt>primedecompose.h</tt>), |
For <code>decompose</code> (and header <tt>primedecompose.h</tt>), |
||
see [[Prime decomposition#C|Prime decomposition]]. |
see [[Prime decomposition#C|Prime decomposition]]. |
||
< |
<syntaxhighlight lang="c">#include <stdbool.h> |
||
#include <gmp.h> |
#include <gmp.h> |
||
#include "primedecompose.h" |
#include "primedecompose.h" |
||
Line 664: | Line 664: | ||
gmp_randclear(rs); |
gmp_randclear(rs); |
||
return res; |
return res; |
||
}</ |
}</syntaxhighlight> |
||
'''Testing''' |
'''Testing''' |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <stdbool.h> |
#include <stdbool.h> |
||
Line 694: | Line 694: | ||
mpz_clear(num); |
mpz_clear(num); |
||
return EXIT_SUCCESS; |
return EXIT_SUCCESS; |
||
}</ |
}</syntaxhighlight> |
||
===Deterministic up to 341,550,071,728,321=== |
===Deterministic up to 341,550,071,728,321=== |
||
< |
<syntaxhighlight lang="c">// calcul a^n%mod |
||
size_t power(size_t a, size_t n, size_t mod) |
size_t power(size_t a, size_t n, size_t mod) |
||
{ |
{ |
||
Line 769: | Line 769: | ||
return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13); |
return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13); |
||
return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13) && witness(n, s, d, 17); |
return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13) && witness(n, s, d, 17); |
||
}</ |
}</syntaxhighlight> |
||
Inspiration from http://stackoverflow.com/questions/4424374/determining-if-a-number-is-prime |
Inspiration from http://stackoverflow.com/questions/4424374/determining-if-a-number-is-prime |
||
===Other version=== |
===Other version=== |
||
It should be a 64-bit deterministic version of the Miller-Rabin primality test. |
It should be a 64-bit deterministic version of the Miller-Rabin primality test. |
||
<syntaxhighlight lang="c"> |
|||
<lang c> |
|||
typedef unsigned long long int ulong; |
typedef unsigned long long int ulong; |
||
Line 813: | Line 813: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">public static class RabinMiller |
||
{ |
{ |
||
public static bool IsPrime(int n, int k) |
public static bool IsPrime(int n, int k) |
||
Line 842: | Line 842: | ||
return true; |
return true; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
[https://stackoverflow.com/questions/7860802/miller-rabin-primality-test] Corrections made 6/21/2017 |
[https://stackoverflow.com/questions/7860802/miller-rabin-primality-test] Corrections made 6/21/2017 |
||
<br><br> |
<br><br> |
||
< |
<syntaxhighlight lang="csharp">// Miller-Rabin primality test as an extension method on the BigInteger type. |
||
// Based on the Ruby implementation on this page. |
// Based on the Ruby implementation on this page. |
||
public static class BigIntegerExtensions |
public static class BigIntegerExtensions |
||
Line 902: | Line 902: | ||
return true; |
return true; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
===Random Approach=== |
===Random Approach=== |
||
< |
<syntaxhighlight lang="lisp">(ns test-p.core |
||
(:require [clojure.math.numeric-tower :as math]) |
(:require [clojure.math.numeric-tower :as math]) |
||
(:require [clojure.set :as set])) |
(:require [clojure.set :as set])) |
||
Line 980: | Line 980: | ||
(println "Is Prime?" 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153 |
(println "Is Prime?" 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153 |
||
(random-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153)) |
(random-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Output}} |
{{Output}} |
||
<pre> |
<pre> |
||
Line 991: | Line 991: | ||
</pre> |
</pre> |
||
===Deterministic Approach=== |
===Deterministic Approach=== |
||
< |
<syntaxhighlight lang="lisp">(ns test-p.core |
||
(:require [clojure.math.numeric-tower :as math])) |
(:require [clojure.math.numeric-tower :as math])) |
||
Line 1,073: | Line 1,073: | ||
(println "Is Prime?" 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153 |
(println "Is Prime?" 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153 |
||
(deterministic-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153)) |
(deterministic-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Output}} |
{{Output}} |
||
<pre> |
<pre> |
||
Line 1,089: | Line 1,089: | ||
=={{header|Commodore BASIC}}== |
=={{header|Commodore BASIC}}== |
||
This displays a minimum probability of primality = 1-1/4<sup>k</sup>, as the fraction of "strong liars" approaches 1/4 in the limit. |
This displays a minimum probability of primality = 1-1/4<sup>k</sup>, as the fraction of "strong liars" approaches 1/4 in the limit. |
||
< |
<syntaxhighlight lang="basic">100 PRINT CHR$(147); CHR$(18); "**** MILLER-RABIN PRIMALITY TEST ****": PRINT |
||
110 INPUT "NUMBER TO TEST"; N$ |
110 INPUT "NUMBER TO TEST"; N$ |
||
120 N = VAL(N$): IF N < 2 THEN 110 |
120 N = VAL(N$): IF N < 2 THEN 110 |
||
Line 1,118: | Line 1,118: | ||
370 P = P * (1 - 1 / (4 * K)) |
370 P = P * (1 - 1 / (4 * K)) |
||
380 IF P THEN PRINT "PROBABLY PRIME ( P >="; P; ")": END |
380 IF P THEN PRINT "PROBABLY PRIME ( P >="; P; ")": END |
||
390 PRINT "COMPOSITE."</ |
390 PRINT "COMPOSITE."</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Sample runs. |
Sample runs. |
||
Line 1,142: | Line 1,142: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang="lisp">(defun factor-out (number divisor) |
||
"Return two values R and E such that NUMBER = DIVISOR^E * R, |
"Return two values R and E such that NUMBER = DIVISOR^E * R, |
||
and R is not divisible by DIVISOR." |
and R is not divisible by DIVISOR." |
||
Line 1,184: | Line 1,184: | ||
thereis (= y (- n 1))))))) |
thereis (= y (- n 1))))))) |
||
(loop repeat k |
(loop repeat k |
||
always (strong-liar? (random-in-range 2 (- n 2)))))))))</ |
always (strong-liar? (random-in-range 2 (- n 2)))))))))</syntaxhighlight> |
||
<pre> |
<pre> |
||
CL-USER> (last (loop for i from 1 to 1000 |
CL-USER> (last (loop for i from 1 to 1000 |
||
Line 1,196: | Line 1,196: | ||
=== Standard non-deterministic M-R test === |
=== Standard non-deterministic M-R test === |
||
< |
<syntaxhighlight lang="ruby">require "big" |
||
module Primes |
module Primes |
||
Line 1,235: | Line 1,235: | ||
puts 341521.prime?(20) # => true |
puts 341521.prime?(20) # => true |
||
puts 341531.prime? # => false</ |
puts 341531.prime? # => false</syntaxhighlight> |
||
=== Deterministic M-R test === |
=== Deterministic M-R test === |
||
Line 1,241: | Line 1,241: | ||
It is a direct translation of the Ruby version for arbitrary sized integers. |
It is a direct translation of the Ruby version for arbitrary sized integers. |
||
It is deterministic for all integers < 3_317_044_064_679_887_385_961_981. |
It is deterministic for all integers < 3_317_044_064_679_887_385_961_981. |
||
< |
<syntaxhighlight lang="ruby"># For crystal >= 0.31.x, compile without overflow check, as either |
||
# crystal build miller-rabin.cr -Ddisable_overflow --release |
# crystal build miller-rabin.cr -Ddisable_overflow --release |
||
# crystal build -Ddisable_overflow miller-rabin.cr --release |
# crystal build -Ddisable_overflow miller-rabin.cr --release |
||
Line 1,384: | Line 1,384: | ||
n = "94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881".to_big_i |
n = "94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881".to_big_i |
||
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs" |
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs" |
||
puts</ |
puts</syntaxhighlight> |
||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="d">import std.random; |
||
bool isProbablePrime(in ulong n, in uint k=10) /*nothrow*/ @safe /*@nogc*/ { |
bool isProbablePrime(in ulong n, in uint k=10) /*nothrow*/ @safe /*@nogc*/ { |
||
Line 1,437: | Line 1,437: | ||
iota(2, 30).filter!isProbablePrime.writeln; |
iota(2, 30).filter!isProbablePrime.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]</pre> |
<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]</pre> |
||
=={{header|E}}== |
=={{header|E}}== |
||
< |
<syntaxhighlight lang="e">def millerRabinPrimalityTest(n :(int > 0), k :int, random) :boolean { |
||
if (n <=> 2 || n <=> 3) { return true } |
if (n <=> 2 || n <=> 3) { return true } |
||
if (n <=> 1 || n %% 2 <=> 0) { return false } |
if (n <=> 1 || n %% 2 <=> 0) { return false } |
||
Line 1,464: | Line 1,464: | ||
} |
} |
||
return true |
return true |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="e">for i ? (millerRabinPrimalityTest(i, 1, entropy)) in 4..1000 { |
||
print(i, " ") |
print(i, " ") |
||
} |
} |
||
println()</ |
println()</syntaxhighlight> |
||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
EchoLisp natively implement the '''prime?''' function = Miller-Rabin tests for big integers. The definition is as follows : |
EchoLisp natively implement the '''prime?''' function = Miller-Rabin tests for big integers. The definition is as follows : |
||
< |
<syntaxhighlight lang="scheme"> |
||
(lib 'bigint) |
(lib 'bigint) |
||
Line 1,512: | Line 1,512: | ||
(prime? (1+ (factorial 100))) ;; native |
(prime? (1+ (factorial 100))) ;; native |
||
→ #f |
→ #f |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir"> |
||
defmodule Prime do |
defmodule Prime do |
||
use Application |
use Application |
||
Line 1,565: | Line 1,565: | ||
end |
end |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,582: | Line 1,582: | ||
</pre> |
</pre> |
||
The following larger examples all produce true: |
The following larger examples all produce true: |
||
< |
<syntaxhighlight lang="elixir"> |
||
miller_rabin?( 94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881, 1000 ) |
miller_rabin?( 94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881, 1000 ) |
||
miller_rabin?( 138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401, 1000 ) |
miller_rabin?( 138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401, 1000 ) |
||
Line 1,590: | Line 1,590: | ||
miller_rabin?( 153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599, 1000 ) |
miller_rabin?( 153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599, 1000 ) |
||
miller_rabin?( 103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041, 1000 ) |
miller_rabin?( 103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041, 1000 ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Line 1,597: | Line 1,597: | ||
to permit use of integers of arbitrary precision. |
to permit use of integers of arbitrary precision. |
||
< |
<syntaxhighlight lang="erlang"> |
||
-module(miller_rabin). |
-module(miller_rabin). |
||
Line 1,687: | Line 1,687: | ||
Acc; |
Acc; |
||
power(B, E, Acc) -> |
power(B, E, Acc) -> |
||
power(B, E - 1, B * Acc).</ |
power(B, E - 1, B * Acc).</syntaxhighlight> |
||
The above code optimised as follows: |
The above code optimised as follows: |
||
Line 1,695: | Line 1,695: | ||
53s to 11s on a quad-core 17 with 16 GB ram. The performance |
53s to 11s on a quad-core 17 with 16 GB ram. The performance |
||
gain from the improved exponentiation was not evaluated. |
gain from the improved exponentiation was not evaluated. |
||
< |
<syntaxhighlight lang="erlang"> |
||
%%% @author Tony Wallace <tony@resurrection> |
%%% @author Tony Wallace <tony@resurrection> |
||
%%% @copyright (C) 2021, Tony Wallace |
%%% @copyright (C) 2021, Tony Wallace |
||
Line 1,879: | Line 1,879: | ||
. |
. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Miller primality test for n<3317044064679887385961981. Nigel Galloway: April 1st., 2021 |
// Miller primality test for n<3317044064679887385961981. Nigel Galloway: April 1st., 2021 |
||
let a=[(2047I,[2I]);(1373653I,[2I;3I]);(9080191I,[31I;73I]);(25326001I,[2I;3I;5I]);(3215031751I,[2I;3I;5I;7I]);(4759123141I,[2I;7I;61I]);(1122004669633I,[2I;13I;23I;1662803I]); |
let a=[(2047I,[2I]);(1373653I,[2I;3I]);(9080191I,[31I;73I]);(25326001I,[2I;3I;5I]);(3215031751I,[2I;3I;5I;7I]);(4759123141I,[2I;7I;61I]);(1122004669633I,[2I;13I;23I;1662803I]); |
||
Line 1,894: | Line 1,894: | ||
printfn "%A %A" (mrP 2147483647I)(mrP 844674407370955389I) |
printfn "%A %A" (mrP 2147483647I)(mrP 844674407370955389I) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,902: | Line 1,902: | ||
Forth only supports native ints (e.g. 64 bits on most modern machines), so this version uses a set of bases that is known to be deterministic for 64 bit integers (and possibly greater). Prior to the Miller Rabin check, the "prime?" word checks for divisibility by some small primes. |
Forth only supports native ints (e.g. 64 bits on most modern machines), so this version uses a set of bases that is known to be deterministic for 64 bit integers (and possibly greater). Prior to the Miller Rabin check, the "prime?" word checks for divisibility by some small primes. |
||
<syntaxhighlight lang="forth"> |
|||
<lang Forth> |
|||
\ modular multiplication and exponentiation |
\ modular multiplication and exponentiation |
||
\ |
\ |
||
Line 1,991: | Line 1,991: | ||
then |
then |
||
then ; |
then ; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
Test on some Fermat numbers and some Mersenne numbers |
Test on some Fermat numbers and some Mersenne numbers |
||
Line 2,006: | Line 2,006: | ||
{{works with|Fortran|95}} |
{{works with|Fortran|95}} |
||
For the module ''PrimeDecompose'', see [[Prime decomposition#Fortran|Prime decomposition]]. |
For the module ''PrimeDecompose'', see [[Prime decomposition#Fortran|Prime decomposition]]. |
||
< |
<syntaxhighlight lang="fortran"> |
||
module Miller_Rabin |
module Miller_Rabin |
||
use PrimeDecompose |
use PrimeDecompose |
||
Line 2,062: | Line 2,062: | ||
end function miller_rabin_test |
end function miller_rabin_test |
||
end module Miller_Rabin</ |
end module Miller_Rabin</syntaxhighlight> |
||
'''Testing''' |
'''Testing''' |
||
< |
<syntaxhighlight lang="fortran">program TestMiller |
||
use Miller_Rabin |
use Miller_Rabin |
||
implicit none |
implicit none |
||
Line 2,087: | Line 2,087: | ||
end subroutine do_test |
end subroutine do_test |
||
end program TestMiller</ |
end program TestMiller</syntaxhighlight> |
||
''Possible improvements'': create bindings to the [[:Category:GMP|GMP library]], change <code>integer(huge)</code> into something like <code>type(huge_integer)</code>, write a lots of interfaces to allow to use big nums naturally (so that the code will be unchanged, except for the changes said above) |
''Possible improvements'': create bindings to the [[:Category:GMP|GMP library]], change <code>integer(huge)</code> into something like <code>type(huge_integer)</code>, write a lots of interfaces to allow to use big nums naturally (so that the code will be unchanged, except for the changes said above) |
||
===With some avoidance of overflow=== |
===With some avoidance of overflow=== |
||
Integer overflow is a severe risk, and even 64-bit integers won't get you far when the formulae are translated as <code>MOD(A**D,N)</code> - what is needed is a method for raising to a power that incorporates the modulus along the way. There is no library routine for that, so... < |
Integer overflow is a severe risk, and even 64-bit integers won't get you far when the formulae are translated as <code>MOD(A**D,N)</code> - what is needed is a method for raising to a power that incorporates the modulus along the way. There is no library routine for that, so... <syntaxhighlight lang="fortran"> MODULE MRTEST !Try the Miller-Rabin primality test. |
||
CONTAINS !Working only with in-built integers. |
CONTAINS !Working only with in-built integers. |
||
LOGICAL FUNCTION MRPRIME(N,TRIALS) !Could N be a prime number? |
LOGICAL FUNCTION MRPRIME(N,TRIALS) !Could N be a prime number? |
||
Line 2,167: | Line 2,167: | ||
END DO |
END DO |
||
END</ |
END</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,285: | Line 2,285: | ||
Using the task pseudo code |
Using the task pseudo code |
||
===Up to 2^63-1=== |
===Up to 2^63-1=== |
||
< |
<syntaxhighlight lang="freebasic">' version 29-11-2016 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 2,385: | Line 2,385: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>9223372036854774893 9223372036854774917 9223372036854774937 |
<pre>9223372036854774893 9223372036854774917 9223372036854774937 |
||
Line 2,399: | Line 2,399: | ||
===Using Big Integer library=== |
===Using Big Integer library=== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang="freebasic">' version 05-04-2017 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Line 2,513: | Line 2,513: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
<pre> 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
||
Line 2,539: | Line 2,539: | ||
Direct implementation of the task algorithm. |
Direct implementation of the task algorithm. |
||
< |
<syntaxhighlight lang="funl">import util.rnd |
||
def isProbablyPrimeMillerRabin( n, k ) = |
def isProbablyPrimeMillerRabin( n, k ) = |
||
Line 2,568: | Line 2,568: | ||
for i <- 3..100 |
for i <- 3..100 |
||
if isProbablyPrimeMillerRabin( i, 5 ) |
if isProbablyPrimeMillerRabin( i, 5 ) |
||
println( i )</ |
println( i )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,606: | Line 2,606: | ||
The main difference between this algorithm and the pseudocode in the task description is that k numbers are not chosen randomly, but instead are the three numbers 2, 7, and 61. These numbers provide a deterministic primality test up to 2^32. |
The main difference between this algorithm and the pseudocode in the task description is that k numbers are not chosen randomly, but instead are the three numbers 2, 7, and 61. These numbers provide a deterministic primality test up to 2^32. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "log" |
import "log" |
||
Line 2,671: | Line 2,671: | ||
} |
} |
||
return true |
return true |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 2,680: | Line 2,680: | ||
* Original Rosetta code has been simplified to be easier to follow |
* Original Rosetta code has been simplified to be easier to follow |
||
Another Miller Rabin test can be found in D. Amos's Haskell for Math module [http://www.polyomino.f2s.com/david/haskell/numbertheory.html Primes.hs] |
Another Miller Rabin test can be found in D. Amos's Haskell for Math module [http://www.polyomino.f2s.com/david/haskell/numbertheory.html Primes.hs] |
||
< |
<syntaxhighlight lang="haskell">module Primes where |
||
import System.Random |
import System.Random |
||
Line 2,724: | Line 2,724: | ||
g i b y | even i = g (i `quot` 2) (b*b `rem` m) y |
g i b y | even i = g (i `quot` 2) (b*b `rem` m) y |
||
| otherwise = f (i-1) b (b*y `rem` m) |
| otherwise = f (i-1) b (b*y `rem` m) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out|Sample output}} |
{{out|Sample output}} |
||
Line 2,741: | Line 2,741: | ||
* The code above likely has better complexity. |
* The code above likely has better complexity. |
||
<syntaxhighlight lang="haskell"> |
|||
<lang Haskell> |
|||
import Control.Monad (liftM) |
import Control.Monad (liftM) |
||
import Data.Bits (Bits, testBit, shiftR) |
import Data.Bits (Bits, testBit, shiftR) |
||
Line 2,797: | Line 2,797: | ||
[n,k] <- liftM (map (\x -> read x :: Integer) . words) getLine |
[n,k] <- liftM (map (\x -> read x :: Integer) . words) getLine |
||
print $ isPrime n k |
print $ isPrime n k |
||
</syntaxhighlight> |
|||
</lang> |
|||
Line 2,818: | Line 2,818: | ||
The following runs in both languages: |
The following runs in both languages: |
||
< |
<syntaxhighlight lang="unicon">procedure main(A) |
||
every n := !A do write(n," is ",(mrp(n,5),"probably prime")|"composite") |
every n := !A do write(n," is ",(mrp(n,5),"probably prime")|"composite") |
||
end |
end |
||
Line 2,850: | Line 2,850: | ||
} |
} |
||
return [s,d] |
return [s,d] |
||
end</ |
end</syntaxhighlight> |
||
Sample run: |
Sample run: |
||
Line 2,870: | Line 2,870: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
The Miller-Rabin primality test is part of the standard library (java.math.BigInteger) |
The Miller-Rabin primality test is part of the standard library (java.math.BigInteger) |
||
< |
<syntaxhighlight lang="java">import java.math.BigInteger; |
||
public class MillerRabinPrimalityTest { |
public class MillerRabinPrimalityTest { |
||
Line 2,878: | Line 2,878: | ||
System.out.println(n.toString() + " is " + (n.isProbablePrime(certainty) ? "probably prime" : "composite")); |
System.out.println(n.toString() + " is " + (n.isProbablePrime(certainty) ? "probably prime" : "composite")); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out|Sample output}} |
{{out|Sample output}} |
||
<pre>java MillerRabinPrimalityTest 123456791234567891234567 1000000 |
<pre>java MillerRabinPrimalityTest 123456791234567891234567 1000000 |
||
Line 2,884: | Line 2,884: | ||
This is a translation of the [http://rosettacode.org/wiki/Miller-Rabin_primality_test#Python:_Proved_correct_up_to_large_N Python solution] for a deterministic test for n < 341,550,071,728,321: |
This is a translation of the [http://rosettacode.org/wiki/Miller-Rabin_primality_test#Python:_Proved_correct_up_to_large_N Python solution] for a deterministic test for n < 341,550,071,728,321: |
||
< |
<syntaxhighlight lang="java">import java.math.BigInteger; |
||
public class Prime { |
public class Prime { |
||
Line 2,963: | Line 2,963: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
For the return values of this function, <code>true</code> means "probably prime" and <code>false</code> means "definitely composite." |
For the return values of this function, <code>true</code> means "probably prime" and <code>false</code> means "definitely composite." |
||
< |
<syntaxhighlight lang="javascript">function probablyPrime(n) { |
||
if (n === 2 || n === 3) return true |
if (n === 2 || n === 3) return true |
||
if (n % 2 === 0 || n < 2) return false |
if (n % 2 === 0 || n < 2) return false |
||
Line 2,991: | Line 2,991: | ||
} |
} |
||
return false |
return false |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
The built-in <code>isprime</code> function uses the Miller-Rabin primality test. Here is the implementation of <code>isprime</code> from the Julia standard library (Julia version 0.2): |
The built-in <code>isprime</code> function uses the Miller-Rabin primality test. Here is the implementation of <code>isprime</code> from the Julia standard library (Julia version 0.2): |
||
< |
<syntaxhighlight lang="julia"> |
||
witnesses(n::Union(Uint8,Int8,Uint16,Int16)) = (2,3) |
witnesses(n::Union(Uint8,Int8,Uint16,Int16)) = (2,3) |
||
witnesses(n::Union(Uint32,Int32)) = n < 1373653 ? (2,3) : (2,7,61) |
witnesses(n::Union(Uint32,Int32)) = n < 1373653 ? (2,3) : (2,7,61) |
||
Line 3,023: | Line 3,023: | ||
return true |
return true |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
Translating the pseudo-code directly rather than using the Java library method BigInteger.isProbablePrime(certainty): |
Translating the pseudo-code directly rather than using the Java library method BigInteger.isProbablePrime(certainty): |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
import java.math.BigInteger |
import java.math.BigInteger |
||
Line 3,079: | Line 3,079: | ||
for (bi in bia) |
for (bi in bia) |
||
println("$bi is ${if (isProbablyPrime(bi, k)) "probably prime" else "composite"}") |
println("$bi is ${if (isProbablyPrime(bi, k)) "probably prime" else "composite"}") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,091: | Line 3,091: | ||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
<syntaxhighlight lang="lb"> |
|||
<lang lb> |
|||
DIM mersenne(11) |
DIM mersenne(11) |
||
mersenne(1)=7 |
mersenne(1)=7 |
||
Line 3,382: | Line 3,382: | ||
End Function |
End Function |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Line 3,388: | Line 3,388: | ||
This implementation of the Miller-Rabin probabilistic primality test is based on the treatment in Chapter 10 of "A Computational Introduction to Number Theory and Algebra" by Victor Shoup. |
This implementation of the Miller-Rabin probabilistic primality test is based on the treatment in Chapter 10 of "A Computational Introduction to Number Theory and Algebra" by Victor Shoup. |
||
< |
<syntaxhighlight lang="lua"> function MRIsPrime(n, k) |
||
-- If n is prime, returns true (without fail). |
-- If n is prime, returns true (without fail). |
||
-- If n is not prime, then returns false with probability ≥ 4^(-k), true otherwise. |
-- If n is not prime, then returns false with probability ≥ 4^(-k), true otherwise. |
||
Line 3,446: | Line 3,446: | ||
end |
end |
||
return z |
return z |
||
end </ |
end </syntaxhighlight> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">MillerRabin[n_,k_]:=Module[{d=n-1,s=0,test=True},While[Mod[d,2]==0 ,d/=2 ;s++] |
||
Do[ |
Do[ |
||
a=RandomInteger[{2,n-1}]; x=PowerMod[a,d,n]; |
a=RandomInteger[{2,n-1}]; x=PowerMod[a,d,n]; |
||
Line 3,457: | Line 3,457: | ||
]; |
]; |
||
,{k}]; |
,{k}]; |
||
Print[test] ]</ |
Print[test] ]</syntaxhighlight> |
||
{{out|Example output (not using the PrimeQ builtin)}} |
{{out|Example output (not using the PrimeQ builtin)}} |
||
< |
<syntaxhighlight lang="mathematica">MillerRabin[17388,10] |
||
->False</ |
->False</syntaxhighlight> |
||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
< |
<syntaxhighlight lang="maxima">/* Miller-Rabin algorithm is builtin, see function primep. Here is another implementation */ |
||
Line 3,510: | Line 3,510: | ||
) |
) |
||
) |
) |
||
)$</ |
)$</syntaxhighlight> |
||
=={{header|Mercury}}== |
=={{header|Mercury}}== |
||
Line 3,531: | Line 3,531: | ||
found with instructions for use in Github. |
found with instructions for use in Github. |
||
<syntaxhighlight lang="mercury"> |
|||
<lang Mercury> |
|||
%----------------------------------------------------------------------% |
%----------------------------------------------------------------------% |
||
:- module primality. |
:- module primality. |
||
Line 3,751: | Line 3,751: | ||
:- end_module test_is_prime. |
:- end_module test_is_prime. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
Line 3,757: | Line 3,757: | ||
===Deterministic approach limited to uint32 values.=== |
===Deterministic approach limited to uint32 values.=== |
||
< |
<syntaxhighlight lang="nim"> |
||
## Nim currently doesn't have a BigInt standard library |
## Nim currently doesn't have a BigInt standard library |
||
## so we translate the version from Go which uses a |
## so we translate the version from Go which uses a |
||
Line 3,831: | Line 3,831: | ||
assert isPrime(492366587u32) |
assert isPrime(492366587u32) |
||
assert isPrime(1645333507u32) |
assert isPrime(1645333507u32) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=== Correct M-R test implementation for using bases > input, deterministic for all integers < 2^64.=== |
=== Correct M-R test implementation for using bases > input, deterministic for all integers < 2^64.=== |
||
< |
<syntaxhighlight lang="nim"> |
||
# Compile as: $ nim c -d:release mrtest.nim |
# Compile as: $ nim c -d:release mrtest.nim |
||
Line 3,977: | Line 3,977: | ||
echo("\nnumber of primes < ",num, " are ", primes.len) |
echo("\nnumber of primes < ",num, " are ", primes.len) |
||
echo (epochTime()-te).formatFloat(ffDecimal, 6) |
echo (epochTime()-te).formatFloat(ffDecimal, 6) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{Header|OCaml}}== |
=={{Header|OCaml}}== |
||
Line 3,983: | Line 3,983: | ||
A direct translation of the wikipedia pseudocode (with <tt>get_rd</tt> helper function translated from <tt>split</tt> in the scheme implementation). This code uses the Zarith and Bigint (bignum) libraries. |
A direct translation of the wikipedia pseudocode (with <tt>get_rd</tt> helper function translated from <tt>split</tt> in the scheme implementation). This code uses the Zarith and Bigint (bignum) libraries. |
||
<syntaxhighlight lang="ocaml"> |
|||
<lang OCaml> |
|||
(* Translated from the wikipedia pseudo-code *) |
(* Translated from the wikipedia pseudo-code *) |
||
let miller_rabin n ~iter:k = |
let miller_rabin n ~iter:k = |
||
Line 4,025: | Line 4,025: | ||
in |
in |
||
loop 0 true |
loop 0 true |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
Line 4,032: | Line 4,032: | ||
the Mercury and Prolog versions on this page. |
the Mercury and Prolog versions on this page. |
||
<syntaxhighlight lang="oz"> |
|||
<lang Oz> |
|||
%--------------------------------------------------------------------------% |
%--------------------------------------------------------------------------% |
||
% module: Primality |
% module: Primality |
||
Line 4,138: | Line 4,138: | ||
% end_module Primality |
% end_module Primality |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
===Built-in=== |
===Built-in=== |
||
< |
<syntaxhighlight lang="parigp">MR(n,k)=ispseudoprime(n,k);</syntaxhighlight> |
||
===Custom=== |
===Custom=== |
||
< |
<syntaxhighlight lang="parigp">sprp(n,b)={ |
||
my(s = valuation(n-1, 2), d = Mod(b, n)^(n >> s)); |
my(s = valuation(n-1, 2), d = Mod(b, n)^(n >> s)); |
||
if (d == 1, return(1)); |
if (d == 1, return(1)); |
||
Line 4,159: | Line 4,159: | ||
); |
); |
||
1 |
1 |
||
};</ |
};</syntaxhighlight> |
||
===Deterministic version=== |
===Deterministic version=== |
||
A basic deterministic test can be obtained by an appeal to the ERH (as proposed by Gary Miller) and a result of Eric Bach (improving on Joseph Oesterlé). Calculations of Jan Feitsma can be used to speed calculations below 2<sup>64</sup> (by a factor of about 250). |
A basic deterministic test can be obtained by an appeal to the ERH (as proposed by Gary Miller) and a result of Eric Bach (improving on Joseph Oesterlé). Calculations of Jan Feitsma can be used to speed calculations below 2<sup>64</sup> (by a factor of about 250). |
||
< |
<syntaxhighlight lang="parigp">A006945=[9, 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051]; |
||
Miller(n)={ |
Miller(n)={ |
||
if (n%2 == 0, return(n == 2)); \\ Handle even numbers |
if (n%2 == 0, return(n == 2)); \\ Handle even numbers |
||
Line 4,181: | Line 4,181: | ||
1 |
1 |
||
) |
) |
||
};</ |
};</syntaxhighlight> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
===Custom=== |
===Custom=== |
||
< |
<syntaxhighlight lang="perl">use bigint try => 'GMP'; |
||
sub is_prime { |
sub is_prime { |
||
Line 4,217: | Line 4,217: | ||
} |
} |
||
print join ", ", grep { is_prime $_, 10 } (1 .. 1000);</ |
print join ", ", grep { is_prime $_, 10 } (1 .. 1000);</syntaxhighlight> |
||
===Modules=== |
===Modules=== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
While normally one would use <tt>is_prob_prime</tt>, <tt>is_prime</tt>, or <tt>is_provable_prime</tt>, which will do a [[wp:Baillie--PSW_primality_test|BPSW test]] and possibly more, we can use just the Miller-Rabin test if desired. For large values we can use an object (e.g. bigint, Math::GMP, Math::Pari, etc.) or just a numeric string. |
While normally one would use <tt>is_prob_prime</tt>, <tt>is_prime</tt>, or <tt>is_provable_prime</tt>, which will do a [[wp:Baillie--PSW_primality_test|BPSW test]] and possibly more, we can use just the Miller-Rabin test if desired. For large values we can use an object (e.g. bigint, Math::GMP, Math::Pari, etc.) or just a numeric string. |
||
< |
<syntaxhighlight lang="perl">use ntheory qw/is_strong_pseudoprime miller_rabin_random/; |
||
sub is_prime_mr { |
sub is_prime_mr { |
||
my $n = shift; |
my $n = shift; |
||
Line 4,231: | Line 4,231: | ||
# Otherwise, perform a number of random base tests, and the result is a probable prime test. |
# Otherwise, perform a number of random base tests, and the result is a probable prime test. |
||
return miller_rabin_random($n, 20); |
return miller_rabin_random($n, 20); |
||
}</ |
}</syntaxhighlight> |
||
Math::Primality also has this functionality, though its function takes only one base and requires the input number to be less than the base. |
Math::Primality also has this functionality, though its function takes only one base and requires the input number to be less than the base. |
||
< |
<syntaxhighlight lang="perl">use Math::Primality qw/is_strong_pseudoprime/; |
||
sub is_prime_mr { |
sub is_prime_mr { |
||
my $n = shift; |
my $n = shift; |
||
Line 4,242: | Line 4,242: | ||
1; |
1; |
||
} |
} |
||
for (1..100) { say if is_prime_mr($_) }</ |
for (1..100) { say if is_prime_mr($_) }</syntaxhighlight> |
||
Math::Pari can be used in a fashion similar to the Pari/GP custom function. The builtin accessed using a second argument to <tt>ispseudoprime</tt> was added to a later version of Pari (the Perl module uses version 2.1.7) so is not accessible directly from Perl. |
Math::Pari can be used in a fashion similar to the Pari/GP custom function. The builtin accessed using a second argument to <tt>ispseudoprime</tt> was added to a later version of Pari (the Perl module uses version 2.1.7) so is not accessible directly from Perl. |
||
Line 4,250: | Line 4,250: | ||
Native-types deterministic version, fails (false negative) at 94,910,107 on 32-bit [fully tested, ie from 1], |
Native-types deterministic version, fails (false negative) at 94,910,107 on 32-bit [fully tested, ie from 1], |
||
and at 4,295,041,217 on 64-bit [only tested from 4,290,000,000] - those limits have now been hard-coded below. |
and at 4,295,041,217 on 64-bit [only tested from 4,290,000,000] - those limits have now been hard-coded below. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">powermod</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">powermod</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span> |
||
Line 4,318: | Line 4,318: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d is %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],{</span><span style="color: #008000;">"composite"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"prime"</span><span style="color: #0000FF;">}[</span><span style="color: #000000;">is_prime_mr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d is %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],{</span><span style="color: #008000;">"composite"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"prime"</span><span style="color: #0000FF;">}[</span><span style="color: #000000;">is_prime_mr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,335: | Line 4,335: | ||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
While desktop/Phix uses a thin wrapper to the builtin gmp routine, the following is also available and is used (after transpilation) in mpfr.js, renamed as mpz_prime: |
While desktop/Phix uses a thin wrapper to the builtin gmp routine, the following is also available and is used (after transpilation) in mpfr.js, renamed as mpz_prime: |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #000080;font-style:italic;">-- this is transpiled (then manually copied) to mpz_prime() in mpfr.js:</span> |
<span style="color: #000080;font-style:italic;">-- this is transpiled (then manually copied) to mpz_prime() in mpfr.js:</span> |
||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">modp47</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span> |
<span style="color: #004080;">mpz</span> <span style="color: #000000;">modp47</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span> |
||
Line 4,438: | Line 4,438: | ||
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> |
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
Either the standard shim or the above can be used as follows |
Either the standard shim or the above can be used as follows |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 4,469: | Line 4,469: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,501: | Line 4,501: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang="php"><?php |
||
function is_prime($n, $k) { |
function is_prime($n, $k) { |
||
if ($n == 2) |
if ($n == 2) |
||
Line 4,539: | Line 4,539: | ||
echo "$i, "; |
echo "$i, "; |
||
echo "\n"; |
echo "\n"; |
||
?></ |
?></syntaxhighlight> |
||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de longRand (N) |
||
(use (R D) |
(use (R D) |
||
(while (=0 (setq R (abs (rand))))) |
(while (=0 (setq R (abs (rand))))) |
||
Line 4,588: | Line 4,588: | ||
(do K |
(do K |
||
(NIL (_prim? N D S)) |
(NIL (_prim? N D S)) |
||
T ) ) ) )</ |
T ) ) ) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>: (filter '((I) (prime? I)) (range 937 1000)) |
<pre>: (filter '((I) (prime? I)) (range 937 1000)) |
||
Line 4,600: | Line 4,600: | ||
=={{header|Pike}}== |
=={{header|Pike}}== |
||
<syntaxhighlight lang="pike"> |
|||
<lang Pike> |
|||
Line 4,692: | Line 4,692: | ||
36261430139487433507414165833468680972181038593593271409697364115931523786727274410257181186996611100786935727 PRIME |
36261430139487433507414165833468680972181038593593271409697364115931523786727274410257181186996611100786935727 PRIME |
||
15579763548573297857414066649875054392128789371879472432457450095645164702139048181789700140949438093329334293 PRIME |
15579763548573297857414066649875054392128789371879472432457450095645164702139048181789700140949438093329334293 PRIME |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Line 4,699: | Line 4,699: | ||
from the Erlang version on this page. |
from the Erlang version on this page. |
||
< |
<syntaxhighlight lang="prolog">:- module(primality, [is_prime/2]). |
||
% is_prime/2 returns false if N is composite, true if N probably prime |
% is_prime/2 returns false if N is composite, true if N probably prime |
||
Line 4,781: | Line 4,781: | ||
; Next_Loop =:= S -> Result = false |
; Next_Loop =:= S -> Result = false |
||
; inner_loop(Next_Base, N, Next_Loop, S, Result) |
; inner_loop(Next_Base, N, Next_Loop, S, Result) |
||
).</ |
).</syntaxhighlight> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">Enumeration |
||
#Composite |
#Composite |
||
#Probably_prime |
#Probably_prime |
||
Line 4,812: | Line 4,812: | ||
Wend |
Wend |
||
ProcedureReturn #Probably_prime |
ProcedureReturn #Probably_prime |
||
EndProcedure</ |
EndProcedure</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
Line 4,820: | Line 4,820: | ||
This versions will give answers with a very small probability of being false. That probability being dependent number of trials (automatically set to 8). |
This versions will give answers with a very small probability of being false. That probability being dependent number of trials (automatically set to 8). |
||
< |
<syntaxhighlight lang="python"> |
||
import random |
import random |
||
Line 4,860: | Line 4,860: | ||
return False |
return False |
||
return True </ |
return True </syntaxhighlight> |
||
===Python: Proved correct up to large N=== |
===Python: Proved correct up to large N=== |
||
Line 4,866: | Line 4,866: | ||
<br>For 341550071728321 and beyond, I have followed the pattern in choosing <code>a</code> from the set of prime numbers.<br>While this uses the best sets known in 1993, there are [http://miller-rabin.appspot.com/ better sets known], and at most 7 are needed for 64-bit numbers. |
<br>For 341550071728321 and beyond, I have followed the pattern in choosing <code>a</code> from the set of prime numbers.<br>While this uses the best sets known in 1993, there are [http://miller-rabin.appspot.com/ better sets known], and at most 7 are needed for 64-bit numbers. |
||
< |
<syntaxhighlight lang="python">def _try_composite(a, d, n, s): |
||
if pow(a, d, n) == 1: |
if pow(a, d, n) == 1: |
||
return False |
return False |
||
Line 4,902: | Line 4,902: | ||
_known_primes = [2, 3] |
_known_primes = [2, 3] |
||
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]</ |
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]</syntaxhighlight> |
||
;Testing: |
;Testing: |
||
Line 4,919: | Line 4,919: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(define (miller-rabin-expmod base exp m) |
(define (miller-rabin-expmod base exp m) |
||
(define (squaremod-with-check x) |
(define (squaremod-with-check x) |
||
Line 4,951: | Line 4,951: | ||
(prime? 4547337172376300111955330758342147474062293202868155909489) ;-> outputs true |
(prime? 4547337172376300111955330758342147474062293202868155909489) ;-> outputs true |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
(formerly Perl 6) |
(formerly Perl 6) |
||
{{works with|Rakudo|2015-09-22}} |
{{works with|Rakudo|2015-09-22}} |
||
<lang |
<syntaxhighlight lang="raku" line># the expmod-function from: http://rosettacode.org/wiki/Modular_exponentiation |
||
sub expmod(Int $a is copy, Int $b is copy, $n) { |
sub expmod(Int $a is copy, Int $b is copy, $n) { |
||
my $c = 1; |
my $c = 1; |
||
Line 4,997: | Line 4,997: | ||
} |
} |
||
say (1..1000).grep({ is_prime($_, 10) }).join(", "); </ |
say (1..1000).grep({ is_prime($_, 10) }).join(", "); </syntaxhighlight> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 5,010: | Line 5,010: | ||
<br>To make the program small, the ''true prime generator'' ('''GenP''') was coded to be small, but not particularly fast. |
<br>To make the program small, the ''true prime generator'' ('''GenP''') was coded to be small, but not particularly fast. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program puts the Miller─Rabin primality test through its paces. */ |
||
parse arg limit times seed . /*obtain optional arguments from the CL*/ |
parse arg limit times seed . /*obtain optional arguments from the CL*/ |
||
if limit=='' | limit=="," then limit= 1000 /*Not specified? Then use the default.*/ |
if limit=='' | limit=="," then limit= 1000 /*Not specified? Then use the default.*/ |
||
Line 5,057: | Line 5,057: | ||
if x\==nL then return 0 /*nope, it ain't prime nohows, noway. */ |
if x\==nL then return 0 /*nope, it ain't prime nohows, noway. */ |
||
end /*k*/ /*maybe it's prime, maybe it ain't ··· */ |
end /*k*/ /*maybe it's prime, maybe it ain't ··· */ |
||
return 1 /*coulda/woulda/shoulda be prime; yup.*/</ |
return 1 /*coulda/woulda/shoulda be prime; yup.*/</syntaxhighlight> |
||
{{out|output|text= when using the input of: <tt> 10000 10 </tt>}} |
{{out|output|text= when using the input of: <tt> 10000 10 </tt>}} |
||
<pre> |
<pre> |
||
Line 5,084: | Line 5,084: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Miller–Rabin primality test |
# Project : Miller–Rabin primality test |
||
Line 5,133: | Line 5,133: | ||
ok |
ok |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 5,144: | Line 5,144: | ||
===Standard Probabilistic=== |
===Standard Probabilistic=== |
||
From 2.5 Ruby has fast modular exponentiation built in. For alternatives prior to 2.5 please see [[Modular_exponentiation#Ruby]] |
From 2.5 Ruby has fast modular exponentiation built in. For alternatives prior to 2.5 please see [[Modular_exponentiation#Ruby]] |
||
< |
<syntaxhighlight lang="ruby">def miller_rabin_prime?(n, g) |
||
d = n - 1 |
d = n - 1 |
||
s = 0 |
s = 0 |
||
Line 5,165: | Line 5,165: | ||
end |
end |
||
p primes = (3..1000).step(2).find_all {|i| miller_rabin_prime?(i,10)}</ |
p primes = (3..1000).step(2).find_all {|i| miller_rabin_prime?(i,10)}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[3, 5, 7, 11, 13, 17, ..., 971, 977, 983, 991, 997]</pre> |
<pre>[3, 5, 7, 11, 13, 17, ..., 971, 977, 983, 991, 997]</pre> |
||
The following larger examples all produce true: |
The following larger examples all produce true: |
||
< |
<syntaxhighlight lang="ruby">puts miller_rabin_prime?(94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881,1000) |
||
puts miller_rabin_prime?(138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401,1000) |
puts miller_rabin_prime?(138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401,1000) |
||
puts miller_rabin_prime?(123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841,1000) |
puts miller_rabin_prime?(123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841,1000) |
||
Line 5,175: | Line 5,175: | ||
puts miller_rabin_prime?(132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731,1000) |
puts miller_rabin_prime?(132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731,1000) |
||
puts miller_rabin_prime?(153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599,1000) |
puts miller_rabin_prime?(153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599,1000) |
||
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000)</ |
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000)</syntaxhighlight> |
||
===Deterministic for integers < 3,317,044,064,679,887,385,961,981=== |
===Deterministic for integers < 3,317,044,064,679,887,385,961,981=== |
||
It extends '''class Integer''' to make it simpler to use. |
It extends '''class Integer''' to make it simpler to use. |
||
< |
<syntaxhighlight lang="ruby">class Integer |
||
# Returns true if +self+ is a prime number, else returns false. |
# Returns true if +self+ is a prime number, else returns false. |
||
def primemr?(k = 10) |
def primemr?(k = 10) |
||
Line 5,302: | Line 5,302: | ||
n = 94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881 |
n = 94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881 |
||
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs" |
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs" |
||
puts</ |
puts</syntaxhighlight> |
||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
Line 5,308: | Line 5,308: | ||
''This code has not been fully tested. Remove this comment after review.'' |
''This code has not been fully tested. Remove this comment after review.'' |
||
< |
<syntaxhighlight lang="runbasic">input "Input a number:";n |
||
input "Input test:";k |
input "Input test:";k |
||
Line 5,362: | Line 5,362: | ||
wend |
wend |
||
[funEnd] |
[funEnd] |
||
END FUNCTION</ |
END FUNCTION</syntaxhighlight> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">/* Add these lines to the [dependencies] section of your Cargo.toml file: |
||
num = "0.2.0" |
num = "0.2.0" |
||
rand = "0.6.5" |
rand = "0.6.5" |
||
Line 5,528: | Line 5,528: | ||
// that n really is a prime number, so return true: |
// that n really is a prime number, so return true: |
||
true |
true |
||
}</ |
}</syntaxhighlight> |
||
'''Test code:''' |
'''Test code:''' |
||
< |
<syntaxhighlight lang="rust">fn main() { |
||
let n = 1234687; |
let n = 1234687; |
||
let result = is_prime(&n); |
let result = is_prime(&n); |
||
Line 5,556: | Line 5,556: | ||
let result = is_prime(&n); |
let result = is_prime(&n); |
||
println!("Q: Is {} prime? A: {}", n, result); |
println!("Q: Is {} prime? A: {}", n, result); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Q: Is 1234687 prime? A: true |
<pre>Q: Is 1234687 prime? A: true |
||
Line 5,566: | Line 5,566: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
{{libheader|Scala}}< |
{{libheader|Scala}}<syntaxhighlight lang="scala">import scala.math.BigInt |
||
object MillerRabinPrimalityTest extends App { |
object MillerRabinPrimalityTest extends App { |
||
val (n, certainty )= (BigInt(args(0)), args(1).toInt) |
val (n, certainty )= (BigInt(args(0)), args(1).toInt) |
||
println(s"$n is ${if (n.isProbablePrime(certainty)) "probably prime" else "composite"}") |
println(s"$n is ${if (n.isProbablePrime(certainty)) "probably prime" else "composite"}") |
||
}</ |
}</syntaxhighlight> |
||
Direct implementation of algorithm: |
Direct implementation of algorithm: |
||
< |
<syntaxhighlight lang="scala"> |
||
import scala.annotation.tailrec |
import scala.annotation.tailrec |
||
import scala.language.{implicitConversions, postfixOps} |
import scala.language.{implicitConversions, postfixOps} |
||
Line 5,613: | Line 5,613: | ||
}) != 1 |
}) != 1 |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
< |
<syntaxhighlight lang="scheme">#!r6rs |
||
(import (rnrs base (6)) |
(import (rnrs base (6)) |
||
(srfi :27 random-bits)) |
(srfi :27 random-bits)) |
||
Line 5,658: | Line 5,658: | ||
(and (> n 1) |
(and (> n 1) |
||
(or (= n 2) |
(or (= n 2) |
||
(pseudoprime? n 50))))</ |
(pseudoprime? n 50))))</syntaxhighlight> |
||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
include "bigint.s7i"; |
include "bigint.s7i"; |
||
Line 5,706: | Line 5,706: | ||
end if; |
end if; |
||
end for; |
end for; |
||
end func;</ |
end func;</syntaxhighlight>Original source: [http://seed7.sourceforge.net/algorith/math.htm#millerRabin] |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func miller_rabin(n, k=10) { |
||
return false if (n <= 1) |
return false if (n <= 1) |
||
Line 5,736: | Line 5,736: | ||
} |
} |
||
say miller_rabin.grep(^1000).join(', ')</ |
say miller_rabin.grep(^1000).join(', ')</syntaxhighlight> |
||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
{{works with|GNU Smalltalk}} |
{{works with|GNU Smalltalk}} |
||
Smalltalk handles big numbers naturally and trasparently (the parent class <tt>Integer</tt> has many subclasses, and <cite>a subclass is picked according to the size</cite> of the integer that must be handled) |
Smalltalk handles big numbers naturally and trasparently (the parent class <tt>Integer</tt> has many subclasses, and <cite>a subclass is picked according to the size</cite> of the integer that must be handled) |
||
< |
<syntaxhighlight lang="smalltalk">Integer extend [ |
||
millerRabinTest: kl [ |k| k := kl. |
millerRabinTest: kl [ |k| k := kl. |
||
self <= 3 |
self <= 3 |
||
Line 5,774: | Line 5,774: | ||
] |
] |
||
] |
] |
||
].</ |
].</syntaxhighlight> |
||
< |
<syntaxhighlight lang="smalltalk">1 to: 1000 do: [ :n | |
||
(n millerRabinTest: 10) ifTrue: [ n printNl ] |
(n millerRabinTest: 10) ifTrue: [ n printNl ] |
||
].</ |
].</syntaxhighlight> |
||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
< |
<syntaxhighlight lang="sml">open LargeInt; |
||
val mr_iterations = Int.toLarge 20; |
val mr_iterations = Int.toLarge 20; |
||
Line 5,828: | Line 5,828: | ||
then (n,t) |
then (n,t) |
||
else findPrime t end |
else findPrime t end |
||
in List.tabulate (10, fn e => findPrime 0) end;</ |
in List.tabulate (10, fn e => findPrime 0) end;</syntaxhighlight> |
||
{{out|Sample run}} |
{{out|Sample run}} |
||
<pre> |
<pre> |
||
Line 5,855: | Line 5,855: | ||
{{libheader|Attaswift BigInt}} |
{{libheader|Attaswift BigInt}} |
||
< |
<syntaxhighlight lang="swift">import BigInt |
||
private let numTrails = 5 |
private let numTrails = 5 |
||
Line 5,891: | Line 5,891: | ||
return true |
return true |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
Use Tcl 8.5 for large integer support |
Use Tcl 8.5 for large integer support |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
proc miller_rabin {n k} { |
proc miller_rabin {n k} { |
||
Line 5,928: | Line 5,928: | ||
puts $i |
puts $i |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 |
<pre>1 |
||
Line 5,947: | Line 5,947: | ||
I've therefore used this method to check the same numbers as in my Kotlin entry. |
I've therefore used this method to check the same numbers as in my Kotlin entry. |
||
< |
<syntaxhighlight lang="ecmascript">import "/big" for BigInt |
||
var iters = 10 |
var iters = 10 |
||
Line 5,963: | Line 5,963: | ||
for (bi in bia) { |
for (bi in bia) { |
||
System.print("%(bi) is %(bi.isProbablePrime(iters) ? "probably prime" : "composite")") |
System.print("%(bi) is %(bi.isProbablePrime(iters) ? "probably prime" : "composite")") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,976: | Line 5,976: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Using the Miller-Rabin primality test in GMP: |
Using the Miller-Rabin primality test in GMP: |
||
< |
<syntaxhighlight lang="zkl">zkl: var BN=Import("zklBigNum"); |
||
zkl: BN("4547337172376300111955330758342147474062293202868155909489").probablyPrime() |
zkl: BN("4547337172376300111955330758342147474062293202868155909489").probablyPrime() |
||
True |
True |
||
zkl: BN("4547337172376300111955330758342147474062293202868155909393").probablyPrime() |
zkl: BN("4547337172376300111955330758342147474062293202868155909393").probablyPrime() |
||
False</ |
False</syntaxhighlight> |