56 lines
948 B
Plaintext
56 lines
948 B
Plaintext
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
|