How to resolve the algorithm Miller–Rabin primality test step by step in the Julia programming language
How to resolve the algorithm Miller–Rabin primality test step by step in the Julia programming language
Table of Contents
Problem Statement
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime or not. The algorithm, as modified by Michael O. Rabin to avoid the generalized Riemann hypothesis, is a probabilistic algorithm. The pseudocode, from Wikipedia is:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Miller–Rabin primality test step by step in the Julia programming language
The code provided is a function in the Julia programming language that tests whether a given integer n
is prime or not. The function is called isprime
and it takes one argument, n
, which is expected to be an integer. The function returns true
if n
is prime, and false
otherwise.
The code begins by checking if n
is equal to 2. If it is, the function returns true
immediately, since 2 is the only even prime number. Next, the code checks if n
is less than 2 or if it is even. If either of these conditions is true, the function returns false
.
If n
is not 2 and is not less than 2 or even, the code proceeds to the main part of the primality test. The first step is to calculate s
, which is the number of trailing zeros in n-1
. The next step is to calculate d
, which is (n-1)
shifted right by s
.
The code then enters a loop that iterates over the witnesses for n
. Witnesses are a set of small prime numbers that can be used to quickly determine whether a larger number is prime or not. The witnesses for n
are determined by its size. If n
is a 8-bit integer, the witnesses are 2 and 3. If n
is a 16-bit integer, the witnesses are 2, 3, and 5. If n
is a 32-bit integer, the witnesses are 2, 3, 5, and 7. If n
is a 64-bit integer, the witnesses are 2, 3, 5, 7, 11, 13, and 17.
For each witness a
, the code first checks if a
is less than n
. If it is, the loop continues to the next witness. Otherwise, the code calculates x
, which is a
raised to the power d
modulo n
. If x
is 1, the loop continues to the next witness. Otherwise, the code enters a nested loop that iterates from s
down to 1. For each iteration of the nested loop, the code calculates x
as x
squared modulo n
. If x
is 1 at any point during this loop, the function returns false
.
If the nested loop completes without x
ever being 1, the function returns true
.
Source code in the julia programming language
witnesses(n::Union(Uint8,Int8,Uint16,Int16)) = (2,3)
witnesses(n::Union(Uint32,Int32)) = n < 1373653 ? (2,3) : (2,7,61)
witnesses(n::Union(Uint64,Int64)) =
n < 1373653 ? (2,3) :
n < 4759123141 ? (2,7,61) :
n < 2152302898747 ? (2,3,5,7,11) :
n < 3474749660383 ? (2,3,5,7,11,13) :
(2,325,9375,28178,450775,9780504,1795265022)
function isprime(n::Integer)
n == 2 && return true
(n < 2) | iseven(n) && return false
s = trailing_zeros(n-1)
d = (n-1) >>> s
for a in witnesses(n)
a < n || break
x = powermod(a,d,n)
x == 1 && continue
t = s
while x != n-1
(t-=1) <= 0 && return false
x = oftype(n, Base.widemul(x,x) % n)
x == 1 && return false
end
end
return true
end
You may also check:How to resolve the algorithm Copy a string step by step in the Babel programming language
You may also check:How to resolve the algorithm The Twelve Days of Christmas step by step in the BCPL programming language
You may also check:How to resolve the algorithm Word wheel step by step in the J programming language
You may also check:How to resolve the algorithm Copy a string step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Vector products step by step in the Phix programming language