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

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

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

Source code in the commodore programming language

100 PRINT CHR$(147); CHR$(18); "****  MILLER-RABIN PRIMALITY TEST   ****": PRINT
110 INPUT "NUMBER TO TEST"; N$
120 N = VAL(N$): IF N < 2 THEN 110
130 IF 0 = (N AND 1) THEN PRINT "(EVEN)": GOTO 380
140 INPUT "ITERATIONS"; K$
150 K = VAL(K$): IF K < 1 THEN 140
160 PRINT
170 DEF FNMD(M) = M - N * INT(M / N)
180 D = N - 1
190 S = 0
200 D = D / 2: S = S + 1
210 IF 0 = (D AND 1) THEN 200
220 P = 1
230 FOR I = 1 TO K
240 : A = INT(RND(.) * (N - 2)) + 2
250 : X = 1
260 : FOR J = 1 TO D
270 :   X = FNMD(X * A)
280 : NEXT J
290 : IF (X = 1) OR (X = (N - 1)) THEN 360
300 : FOR J = 1 TO S - 1
310 :   X = FNMD(X * X)
320 :   IF X = 1 THEN P = 0: GOTO 370
330 :   IF X = N - 1 THEN 360
340 : NEXT J
350 : P = 0: GOTO 370
360 NEXT I
370 P = P * (1 - 1 / (4 * K))
380 IF P THEN PRINT "PROBABLY PRIME ( P >="; P; ")": END
390 PRINT "COMPOSITE."

You may also check:How to resolve the algorithm Pell's equation step by step in the Phix programming language
You may also check:How to resolve the algorithm Count in octal step by step in the Dc programming language
You may also check:How to resolve the algorithm Sort an integer array step by step in the C# programming language
You may also check:How to resolve the algorithm Rock-paper-scissors step by step in the Haskell programming language
You may also check:How to resolve the algorithm Five weekends step by step in the Ada programming language