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

Published on 12 May 2024 09:40 PM
#Run basic

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

Source code in the run programming language

input "Input a number:";n
input "Input test:";k

test =  millerRabin(n,k)
if test = 0 then 
  print "Probably Prime"
 else
  print "Composite"
end if
wait

' ----------------------------------------
' Returns 
'  Composite     = 1
'  Probably Prime = 0
' ----------------------------------------
 FUNCTION millerRabin(n, k)
  if n = 2 then
    millerRabin = 0 'probablyPrime
    goto [funEnd]
  end if

  if n mod 2 = 0 or n < 2 then
    millerRabin = 1 'composite
    goto [funEnd]
  end if

d = n - 1
while d mod 2 = 0
  d = d / 2
  s = s + 1
wend
  
while k > 0
  k = k - 1
  base = 2 + int(rnd(1)*(n-3))
  x = (base^d) mod n
  if x <> 1 and x <> n-1 then
    for r=1 To s-1
      x =(x * x) mod n
      if x=1 then
       millerRabin = 1 ' composite 
       goto [funEnd]
      end if
      if x = n-1 then exit for
    next r
    
    if x<>n-1 then
      millerRabin =  1 ' composite 
      goto [funEnd]
    end if
  end if
wend
[funEnd]
END FUNCTION

You may also check:How to resolve the algorithm Read a file line by line step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Caesar cipher step by step in the langur programming language
You may also check:How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Julia programming language
You may also check:How to resolve the algorithm Averages/Mean time of day step by step in the Tcl programming language
You may also check:How to resolve the algorithm Sorting algorithms/Quicksort step by step in the FreeBASIC programming language