Miller–Rabin primality test: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,000: / Line 1,000: @@
 =={{header|Commodore BASIC}}==
+This displays a minimum probability of primality = 1-1/4<sup>k</sup>, as the fraction of "strong liars" approaches 1/4 in the limit.
-<lang basic>100 PRINT CHR$(147)CHR$(18)"****  MILLER-RABIN PRIMALITY TEST   ****": PRINT
+<lang basic>100 PRINT CHR$(147); CHR$(18); "****  MILLER-RABIN PRIMALITY TEST   ****": PRINT
-OPEN 1, 0
+INPUT "NUMBER TO TEST"; N$
-PRINT "ENTER N:";: INPUT#1, N$: PRINT
-N = VAL(N$): IF N<2 THEN 120
+N = VAL(N$): IF N < 2 THEN 110
-IF 0 = (N AND 1) THEN PRINT "(EVEN)": GOTO 400
+IF 0 = (N AND 1) THEN PRINT "(EVEN)": GOTO 380
+INPUT "ITERATIONS"; K$
-PRINT "ENTER K:";: INPUT#1, K$: PRINT
-K = VAL(K$): IF K < 1 THEN 150
+K = VAL(K$): IF K < 1 THEN 140
+PRINT
-CLOSE 1
+DEF FNMD(M) = M - N * INT(M / N)
 D = N - 1
 S = 0
@@ Line 1,017: / Line 1,018: @@
 : X = 1
 : FOR J = 1 TO D
-:   X = X * A
+:   X = FNMD(X * A)
-:   X = X - N * INT(X / N)
+: NEXT J
+: IF (X = 1) OR (X = (N - 1)) THEN 360
-: NEXT J
-: IF (X = 1) OR (X = (N - 1)) THEN 380
+: FOR J = 1 TO S - 1
-: FOR J = 1 TO S - 1
+:   X = FNMD(X * X)
-:   X = X * X
+:   IF X = 1 THEN P = 0: GOTO 370
-:   X = X - N * INT(X / N)
+:   IF X = N - 1 THEN 360
+: NEXT J
-:   IF X = 1 THEN P = 0: GOTO 390
-:   IF X = N - 1 THEN 380
+: P = 0: GOTO 370
-: NEXT J
+NEXT I
-: P = 0: GOTO 390
+P = P * (1 - 1 / (4 * K))
+IF P THEN PRINT "PROBABLY PRIME ( P >="; P; ")": END
-NEXT I
+PRINT "COMPOSITE."</lang>
-P = P * (1 - 1 / (4 * K))
-IF P THEN PRINT "PROBABLY PRIME (P >="P")": END
-PRINT "COMPOSITE."</lang>
 {{Out}}
+Sample runs.
-Sample runs. Probability of primality is is computed as 1-1/4<sup>k</sup>, based on the fraction of "strong liars" which approaches 1/4 in the limit.
 <pre>****  MILLER-RABIN PRIMALITY TEST   ****
-ENTER N:1747
+NUMBER TO TEST? 1747
-ENTER K:2
+ITERATIONS? 2
-PROBABLY PRIME (P >= .875 )
+PROBABLY PRIME ( P >= .875 )
 READY.</pre>
@@ Line 1,044: / Line 1,045: @@
 <pre>****  MILLER-RABIN PRIMALITY TEST   ****
-ENTER N:4353
-ENTER K:2
-COMPOSITE.
+NUMBER TO TEST? 32329
-READY.</pre>
+ITERATIONS? 2
+COMPOSITE.</pre>
-(Self-evident, since 4+3+5+3=15 is a multiple of 3.)
 =={{header|Common Lisp}}==