31 lines
837 B
Plaintext
31 lines
837 B
Plaintext
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."
|