Miller–Rabin primality test: Difference between revisions
no edit summary
(→{{header|REXX}}: added/changed comments and whitespace, changed indentations, optimized the inner DO loop in the M_Rt function.) |
No edit summary |
||
Line 3,880:
─────────────────────────────────────────────────────────────────────────────────────────
for 1──►10000, K=10, Miller─Rabin primality test found 1229 primes {out of 1229}.
</pre>
=={{header|Ring}}==
<lang ring>
# Project : Miller–Rabin primality test
# Date : 2017/11/17
# Author : Gal Zsolt (~ CalmoSoft ~)
# Email : <calmosoft@gmail.com>
see "Input a number: " give n
see "Input test: " give k
test = millerrabin(n,k)
if test = 0
see "Probably Prime" + nl
else
see "Composite" + nl
ok
func millerrabin(n, k)
if n = 2
millerRabin = 0
return millerRabin
ok
if n % 2 = 0 or n < 2
millerRabin = 1
return millerRabin
ok
d = n - 1
s = 0
while d % 2 = 0
d = d / 2
s = s + 1
end
while k > 0
k = k - 1
base = 2 + floor((random(10)/10)*(n-3))
x = pow(base, d) % n
if x != 1 and x != n-1
for r=1 to s-1
x = (x * x) % n
if x = 1
millerRabin = 1
return millerRabin
ok
if x = n-1
exit
ok
next
if x != n-1
millerRabin = 1
return millerRabin
ok
ok
end
</lang>
Output:
<pre>
Input a number: 17
Input test: 8
Probably Prime
</pre>
| |||