How to resolve the algorithm Miller–Rabin primality test step by step in the Julia programming language

Published on 22 June 2024 08:30 PM

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