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

Published on 12 May 2024 09:40 PM
#Sidef

How to resolve the algorithm Miller–Rabin primality test step by step in the Sidef 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 Sidef programming language

Source code in the sidef programming language

func miller_rabin(n, k=10) {

    return false if (n <= 1)
    return true  if (n == 2)
    return false if (n.is_even)

    var t = n-1
    var s = t.valuation(2)
    var d = t>>s

    k.times {
        var a = irand(2, t)
        var x = powmod(a, d, n)
        next if (x ~~ [1, t])

        (s-1).times {
            x.powmod!(2, n)
            return false if (x == 1)
            break if (x == t)
        }

        return false if (x != t)
    }

    return true
}

say miller_rabin.grep(^1000).join(', ')

You may also check:How to resolve the algorithm Hello world/Graphical step by step in the Phix programming language
You may also check:How to resolve the algorithm Greatest common divisor step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm String comparison step by step in the Elixir programming language
You may also check:How to resolve the algorithm Here document step by step in the Mathematica / Wolfram Language programming language
You may also check:How to resolve the algorithm Rot-13 step by step in the LiveCode programming language