Miller–Rabin primality test: Difference between revisions

{{trans|D}}

 

I n < 2 | n % 2 == 0

R n == 2

R 1B

 

 

{{out}}

such as for the [[Carmichael 3 strong pseudoprimes]] the [[Extensible prime generator]], and the [[Emirp primes]].

 

type Number is range <>;

package Miller_Rabin is

function Is_Prime (N : Number; K : Positive := 10) return Result_Type;

 

 

The implementation of that package is as follows:

 

 

package body Miller_Rabin is

end Is_Prime;

 

 

Finally, the program itself:

 

 

procedure Mr_Tst is

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)));

 

{{out}}

Using the big integer implementation from a cryptographic library [https://github.com/cforler/Ada-Crypto-Library/].

 

 

procedure Miller_Rabin is

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)));

 

{{out}}

Using the built-in Miller-Rabin test from the same library:

 

 

procedure Miller_Rabin is

Ada.Text_IO.Put_Line("Prime(" & T & ")="

& Boolean'Image (LN.Mod_Utils.Passed_Miller_Rabin_Test(+T, K)));

 

The output is the same.

{{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 }} -->

MODE LOOPINT = INT;

 

print((" ",whole(i,0)))

FI

{{out}}

<pre>

=={{header|AutoHotkey}}==

ahk forum: [http://www.autohotkey.com/forum/post-276712.html#276712 discussion]

MsgBox % MillerRabin(999809,10) ; 1

MsgBox % MillerRabin(999727,10) ; 1

y := i&1 ? mod(y*z,m) : y, z := mod(z*z,m), i >>= 1

Return y

 

=={{header|bc}}==

{{works with|OpenBSD bc}}

(A previous version worked with [[GNU bc]].)

scale = 0

 

}

}

 

=={{header|BQN}}==

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.

 

MillerRabin ← { 𝕊n: 10𝕊n ; iter 𝕊 n: !2|n

# n = 1 + d×2⋆s

C ← { 𝕊a: s MR a Pow d } # Is composite

{0:1; C •rand.Range⌾(-⟜2) n ? 0; 𝕊𝕩-1} iter

 

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.

 

_modMul ← { n _𝕣:

# Split each argument into two 26-bit numbers, with the remaining

Mul ← × (⊣ ⋈ -⊸(+´)) ·⥊×⌜○Split

((n×<⟜0)⊸+ -⟜n+⊢)´ n | Mul

 

{{out}}

 

1

MillerRabin¨⊸/ 101+2×↕10

 

=={{header|Bracmat}}==

{{trans|bc}}

& ( rand

=

& !primes:? [-11 ?last

& out$!last

{{out}}

<pre>937 941 947 953 967 971 977 983 991 997</pre>

{{libheader|GMP}}

'''miller-rabin.h'''

#define _MILLER_RABIN_H

#include <gmp.h>

bool miller_rabin_test(mpz_t n, int j);

'''miller-rabin.c'''

{{trans|Fortran}}

For <code>decompose</code> (and header <tt>primedecompose.h</tt>),

see [[Prime decomposition#C|Prime decomposition]].

#include <gmp.h>

#include "primedecompose.h"

gmp_randclear(rs);

return res;

'''Testing'''

#include <stdlib.h>

#include <stdbool.h>

mpz_clear(num);

return EXIT_SUCCESS;

 

 

===Deterministic up to 341,550,071,728,321===

size_t power(size_t a, size_t n, size_t mod)

{

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);

Inspiration from http://stackoverflow.com/questions/4424374/determining-if-a-number-is-prime

 

===Other version===

It should be a 64-bit deterministic version of the Miller-Rabin primality test.

typedef unsigned long long int ulong;

 

}

 

 

=={{header|C sharp|C#}}==

{

public static bool IsPrime(int n, int k)

return true;

}

[https://stackoverflow.com/questions/7860802/miller-rabin-primality-test] Corrections made 6/21/2017

<br><br>

// Based on the Ruby implementation on this page.

public static class BigIntegerExtensions

return true;

}

 

=={{header|Clojure}}==

===Random Approach===

(:require [clojure.math.numeric-tower :as math])

(:require [clojure.set :as set]))

(println "Is Prime?" 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153

(random-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153))

{{Output}}

<pre>

</pre>

===Deterministic Approach===

(:require [clojure.math.numeric-tower :as math]))

 

(println "Is Prime?" 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153

(deterministic-test 743808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153))

{{Output}}

<pre>

=={{header|Commodore BASIC}}==

This displays a minimum probability of primality = 1-1/4^k, as the fraction of "strong liars" approaches 1/4 in the limit.

110 INPUT "NUMBER TO TEST"; N$

120 N = VAL(N$): IF N < 2 THEN 110

370 P = P * (1 - 1 / (4 * K))

380 IF P THEN PRINT "PROBABLY PRIME ( P >="; P; ")": END

{{Out}}

Sample runs.

 

=={{header|Common Lisp}}==

"Return two values R and E such that NUMBER = DIVISOR^E * R,

and R is not divisible by DIVISOR."

thereis (= y (- n 1)))))))

(loop repeat k

<pre>

CL-USER> (last (loop for i from 1 to 1000

=== Standard non-deterministic M-R test ===

 

 

module Primes

 

puts 341521.prime?(20) # => true

 

=== Deterministic M-R test ===

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.

# crystal build miller-rabin.cr -Ddisable_overflow --release

# crystal build -Ddisable_overflow miller-rabin.cr --release

n = "94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881".to_big_i

print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"

 

=={{header|D}}==

{{trans|Ruby}}

 

bool isProbablePrime(in ulong n, in uint k=10) /*nothrow*/ @safe /*@nogc*/ {

 

iota(2, 30).filter!isProbablePrime.writeln;

{{out}}

<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]</pre>

 

=={{header|E}}==

if (n <=> 2 || n <=> 3) { return true }

if (n <=> 1 || n %% 2 <=> 0) { return false }

}

return true

print(i, " ")

}

 

=={{header|EchoLisp}}==

EchoLisp natively implement the '''prime?''' function = Miller-Rabin tests for big integers. The definition is as follows :

(lib 'bigint)

 

(prime? (1+ (factorial 100))) ;; native

→ #f

 

=={{header|Elixir}}==

defmodule Prime do

use Application

end

end

 

{{out}}

</pre>

The following larger examples all produce true:

miller_rabin?( 94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881, 1000 )

miller_rabin?( 138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401, 1000 )

miller_rabin?( 153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599, 1000 )

miller_rabin?( 103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041, 1000 )

 

=={{header|Erlang}}==

to permit use of integers of arbitrary precision.

 

-module(miller_rabin).

 

Acc;

power(B, E, Acc) ->

 

The above code optimised as follows:

53s to 11s on a quad-core 17 with 16 GB ram. The performance

gain from the improved exponentiation was not evaluated.

%%% @author Tony Wallace <tony@resurrection>

%%% @copyright (C) 2021, Tony Wallace

.

 

 

=={{header|F_Sharp|F#}}==

// 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]);

 

printfn "%A %A" (mrP 2147483647I)(mrP 844674407370955389I)

{{out}}

<pre>

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.

 

\ modular multiplication and exponentiation

\

then

then ;

{{Out}}

Test on some Fermat numbers and some Mersenne numbers

{{works with|Fortran|95}}

For the module ''PrimeDecompose'', see [[Prime decomposition#Fortran|Prime decomposition]].

module Miller_Rabin

use PrimeDecompose

end function miller_rabin_test

 

'''Testing'''

use Miller_Rabin

implicit none

end subroutine do_test

''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===

CONTAINS !Working only with in-built integers.

LOGICAL FUNCTION MRPRIME(N,TRIALS) !Could N be a prime number?

END DO

 

Output:

<pre>

Using the task pseudo code

===Up to 2^63-1===

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>9223372036854774893 9223372036854774917 9223372036854774937

===Using Big Integer library===

{{libheader|GMP}}

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{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

Direct implementation of the task algorithm.

 

 

def isProbablyPrimeMillerRabin( n, k ) =

for i <- 3..100

if isProbablyPrimeMillerRabin( i, 5 )

 

{{out}}

 

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.

 

import "log"

}

return true

 

=={{header|Haskell}}==

* 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]

 

import System.Random

g i b y | even i = g (i `quot` 2) (b*b `rem` m) y

| otherwise = f (i-1) b (b*y `rem` m)

 

{{out|Sample output}}

* The code above likely has better complexity.

 

import Control.Monad (liftM)

import Data.Bits (Bits, testBit, shiftR)

[n,k] <- liftM (map (\x -> read x :: Integer) . words) getLine

print $ isPrime n k

 

 

 

The following runs in both languages:

every n := !A do write(n," is ",(mrp(n,5),"probably prime")|"composite")

end

}

return [s,d]

 

Sample run:

=={{header|Java}}==

The Miller-Rabin primality test is part of the standard library (java.math.BigInteger)

 

public class MillerRabinPrimalityTest {

System.out.println(n.toString() + " is " + (n.isProbablePrime(certainty) ? "probably prime" : "composite"));

}

{{out|Sample output}}

<pre>java MillerRabinPrimalityTest 123456791234567891234567 1000000

 

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:

 

public class Prime {

}

}

 

=={{header|JavaScript}}==

For the return values of this function, <code>true</code> means "probably prime" and <code>false</code> means "definitely composite."

 

if (n === 2 || n === 3) return true

if (n % 2 === 0 || n < 2) return false

}

return false

 

=={{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):

witnesses(n::Union(Uint8,Int8,Uint16,Int16)) = (2,3)

witnesses(n::Union(Uint32,Int32)) = n < 1373653 ? (2,3) : (2,7,61)

return true

end

 

=={{header|Kotlin}}==

Translating the pseudo-code directly rather than using the Java library method BigInteger.isProbablePrime(certainty):

 

import java.math.BigInteger

for (bi in bia)

println("$bi is ${if (isProbablyPrime(bi, k)) "probably prime" else "composite"}")

 

{{out}}

 

=={{header|Liberty BASIC}}==

DIM mersenne(11)

mersenne(1)=7

 

End Function

 

=={{header|Lua}}==

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.

 

-- If n is prime, returns true (without fail).

-- If n is not prime, then returns false with probability ≥ 4^(-k), true otherwise.

end

return z

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Do[

a=RandomInteger[{2,n-1}]; x=PowerMod[a,d,n];

];

,{k}];

{{out|Example output (not using the PrimeQ builtin)}}

 

=={{header|Maxima}}==

 

 

 

)

)

 

=={{header|Mercury}}==

found with instructions for use in Github.

 

%----------------------------------------------------------------------%

:- module primality.

:- end_module test_is_prime.

 

 

=={{header|Nim}}==

===Deterministic approach limited to uint32 values.===

 

## Nim currently doesn't have a BigInt standard library

## so we translate the version from Go which uses a

assert isPrime(492366587u32)

assert isPrime(1645333507u32)

 

=== Correct M-R test implementation for using bases > input, deterministic for all integers < 2^64.===

 

 

# Compile as: $ nim c -d:release mrtest.nim

echo("\nnumber of primes < ",num, " are ", primes.len)

echo (epochTime()-te).formatFloat(ffDecimal, 6)

 

=={{Header|OCaml}}==

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.

 

(* Translated from the wikipedia pseudo-code *)

let miller_rabin n ~iter:k =

in

loop 0 true

 

=={{header|Oz}}==

the Mercury and Prolog versions on this page.

 

%--------------------------------------------------------------------------%

% module: Primality

% end_module Primality

 

 

=={{header|PARI/GP}}==

===Built-in===

===Custom===

my(s = valuation(n-1, 2), d = Mod(b, n)^(n >> s));

if (d == 1, return(1));

);

1

===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⁶⁴ (by a factor of about 250).

Miller(n)={

if (n%2 == 0, return(n == 2)); \\ Handle even numbers

1

)

 

=={{header|Perl}}==

 

===Custom===

 

sub is_prime {

}

 

 

===Modules===

{{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.

sub is_prime_mr {

my $n = shift;

# Otherwise, perform a number of random base tests, and the result is a probable prime test.

return miller_rabin_random($n, 20);

Math::Primality also has this functionality, though its function takes only one base and requires the input number to be less than the base.

sub is_prime_mr {

my $n = shift;

1;

}

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.

 

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.

<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: #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>

{{out}}

<pre>

{{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:

<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: #008080;">return</span> <span style="color: #004600;">true</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>

Either the standard shim or the above can be used as follows

<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;">end</span> <span style="color: #008080;">if</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

{{out}}

<pre>

 

=={{header|PHP}}==

function is_prime($n, $k) {

if ($n == 2)

echo "$i, ";

echo "\n";

 

=={{header|PicoLisp}}==

(use (R D)

(while (=0 (setq R (abs (rand)))))

(do K

(NIL (_prim? N D S))

{{out}}

<pre>: (filter '((I) (prime? I)) (range 937 1000))

 

=={{header|Pike}}==

 

 

36261430139487433507414165833468680972181038593593271409697364115931523786727274410257181186996611100786935727 PRIME

15579763548573297857414066649875054392128789371879472432457450095645164702139048181789700140949438093329334293 PRIME

 

=={{header|Prolog}}==

from the Erlang version on this page.

 

 

% is_prime/2 returns false if N is composite, true if N probably prime

; Next_Loop =:= S -> Result = false

; inner_loop(Next_Base, N, Next_Loop, S, Result)

 

=={{header|PureBasic}}==

#Composite

#Probably_prime

Wend

ProcedureReturn #Probably_prime

 

=={{header|Python}}==

This versions will give answers with a very small probability of being false. That probability being dependent number of trials (automatically set to 8).

 

 

import random

return False

 

===Python: Proved correct up to large N===

<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.

 

if pow(a, d, n) == 1:

return False

 

_known_primes = [2, 3]

 

;Testing:

 

=={{header|Racket}}==

(define (miller-rabin-expmod base exp m)

(define (squaremod-with-check x)

 

(prime? 4547337172376300111955330758342147474062293202868155909489) ;-> outputs true

 

=={{header|Raku}}==

(formerly Perl 6)

{{works with|Rakudo|2015-09-22}}

sub expmod(Int $a is copy, Int $b is copy, $n) {

my $c = 1;

}

 

 

=={{header|REXX}}==

 

<br>To make the program small, the &nbsp; ''true prime generator'' &nbsp; ('''GenP''') &nbsp; was coded to be small, but not particularly fast.

parse arg limit times seed . /*obtain optional arguments from the CL*/

if limit=='' | limit=="," then limit= 1000 /*Not specified? Then use the default.*/

if x\==nL then return 0 /*nope, it ain't prime nohows, noway. */

end /*k*/ /*maybe it's prime, maybe it ain't ··· */

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> 10000 &nbsp; 10 </tt>}}

<pre>

 

=={{header|Ring}}==

# Project : Miller–Rabin primality test

 

ok

end

Output:

<pre>

===Standard Probabilistic===

From 2.5 Ruby has fast modular exponentiation built in. For alternatives prior to 2.5 please see [[Modular_exponentiation#Ruby]]

d = n - 1

s = 0

end

 

{{out}}

<pre>[3, 5, 7, 11, 13, 17, ..., 971, 977, 983, 991, 997]</pre>

The following larger examples all produce true:

puts miller_rabin_prime?(138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401,1000)

puts miller_rabin_prime?(123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841,1000)

puts miller_rabin_prime?(132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731,1000)

puts miller_rabin_prime?(153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599,1000)

 

===Deterministic for integers < 3,317,044,064,679,887,385,961,981===

It extends '''class Integer''' to make it simpler to use.

# Returns true if +self+ is a prime number, else returns false.

def primemr?(k = 10)

n = 94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881

print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"

 

=={{header|Run BASIC}}==

''This code has not been fully tested. Remove this comment after review.''

 

input "Input test:";k

 

wend

[funEnd]

 

=={{header|Rust}}==

 

num = "0.2.0"

rand = "0.6.5"

// that n really is a prime number, so return true:

true

 

'''Test code:'''

 

let n = 1234687;

let result = is_prime(&n);

let result = is_prime(&n);

println!("Q: Is {} prime? A: {}", n, result);

{{out}}

<pre>Q: Is 1234687 prime? A: true

 

=={{header|Scala}}==

 

object MillerRabinPrimalityTest extends App {

val (n, certainty )= (BigInt(args(0)), args(1).toInt)

println(s"$n is ${if (n.isProbablePrime(certainty)) "probably prime" else "composite"}")

 

Direct implementation of algorithm:

 

import scala.annotation.tailrec

import scala.language.{implicitConversions, postfixOps}

}) != 1

}

 

=={{header|Scheme}}==

(import (rnrs base (6))

(srfi :27 random-bits))

(and (> n 1)

(or (= n 2)

 

=={{header|Seed7}}==

include "bigint.s7i";

end if;

end for;

 

=={{header|Sidef}}==

 

return false if (n <= 1)

}

 

 

=={{header|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)

millerRabinTest: kl [ |k| k := kl.

self <= 3

]

]

(n millerRabinTest: 10) ifTrue: [ n printNl ]

 

=={{header|Standard ML}}==

 

val mr_iterations = Int.toLarge 20;

then (n,t)

else findPrime t end

{{out|Sample run}}

<pre>

{{libheader|Attaswift BigInt}}

 

 

private let numTrails = 5

 

return true

 

=={{header|Tcl}}==

Use Tcl 8.5 for large integer support

 

proc miller_rabin {n k} {

puts $i

}

{{out}}

<pre>1

 

I've therefore used this method to check the same numbers as in my Kotlin entry.

 

var iters = 10

for (bi in bia) {

System.print("%(bi) is %(bi.isProbablePrime(iters) ? "probably prime" : "composite")")

 

{{out}}

=={{header|zkl}}==

Using the Miller-Rabin primality test in GMP:

zkl: BN("4547337172376300111955330758342147474062293202868155909489").probablyPrime()

True

zkl: BN("4547337172376300111955330758342147474062293202868155909393").probablyPrime()