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

Published on 12 May 2024 09:40 PM
#E

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

Source code in the e programming language

def millerRabinPrimalityTest(n :(int > 0), k :int, random) :boolean {
  if (n <=> 2 || n <=> 3) { return true }
  if (n <=> 1 || n %% 2 <=> 0) { return false }
  var d := n - 1
  var s := 0
  while (d %% 2 <=> 0) {
    d //= 2
    s += 1
  }
  for _ in 1..k {
     def nextTrial := __continue
     def a := random.nextInt(n - 3) + 2     # [2, n - 2] = [0, n - 4] + 2 = [0, n - 3) + 2
     var x := a**d %% n                     # Note: Will do optimized modular exponentiation
     if (x <=> 1 || x <=> n - 1) { nextTrial() }
     for _ in 1 .. (s - 1) {
        x := x**2 %% n
        if (x <=> 1) { return false }
        if (x <=> n - 1) { nextTrial() }
     }
     return false
  }
  return true
}

for i ? (millerRabinPrimalityTest(i, 1, entropy)) in 4..1000 {
  print(i, " ")
}
println()

You may also check:How to resolve the algorithm Named parameters step by step in the SenseTalk programming language
You may also check:How to resolve the algorithm Sorting algorithms/Merge sort step by step in the Rust programming language
You may also check:How to resolve the algorithm Stable marriage problem step by step in the BBC BASIC programming language
You may also check:How to resolve the algorithm Determine if a string is squeezable step by step in the C programming language
You may also check:How to resolve the algorithm Calculating the value of e step by step in the Racket programming language