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

Published on 12 May 2024 09:40 PM
#Picolisp

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

Source code in the picolisp programming language

(de longRand (N)
   (use (R D)
      (while (=0 (setq R (abs (rand)))))
      (until (> R N)
         (unless (=0 (setq D (abs (rand))))
            (setq R (* R D)) ) )
      (% R N) ) )

(de **Mod (X Y N)
   (let M 1
      (loop
         (when (bit? 1 Y)
            (setq M (% (* M X) N)) )
         (T (=0 (setq Y (>> 1 Y)))
            M )
         (setq X (% (* X X) N)) ) ) )

(de _prim? (N D S)
   (use (A X R)
      (while (> 2 (setq A (longRand N))))
      (setq R 0  X (**Mod A D N))
      (loop
         (T
            (or
               (and (=0 R) (= 1 X))
               (= X (dec N)) )
            T )
         (T
            (or
               (and (> R 0) (= 1 X))
               (>= (inc 'R) S) )
            NIL )
         (setq X (% (* X X) N)) ) ) )

(de prime? (N K)
   (default K 50)
   (and
      (> N 1)
      (bit? 1 N)
      (let (D (dec N)  S 0)
         (until (bit? 1 D)
            (setq
               D  (>> 1 D)
               S  (inc S) ) )
         (do K
            (NIL (_prim? N D S))
            T ) ) ) )

You may also check:How to resolve the algorithm The Twelve Days of Christmas step by step in the Rust programming language
You may also check:How to resolve the algorithm Variable declaration reset step by step in the Go programming language
You may also check:How to resolve the algorithm AKS test for primes step by step in the 8th programming language
You may also check:How to resolve the algorithm Sockets step by step in the R programming language
You may also check:How to resolve the algorithm Determinant and permanent step by step in the Forth programming language