Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(smalltalk) |
(add Tcl) |
||
Line 323: | Line 323: | ||
(n millerRabinTest: 10) ifTrue: [ n printNl ] |
(n millerRabinTest: 10) ifTrue: [ n printNl ] |
||
].</lang> |
].</lang> |
||
=={{header|Tcl}}== |
|||
Use Tcl 8.5 for large integer support |
|||
<lang tcl>package require Tcl 8.5 |
|||
proc miller_rabin {n k} { |
|||
if {$n <= 3} {return true} |
|||
if {$n % 2 == 0} {return false} |
|||
# write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1 |
|||
set d [expr {$n - 1}] |
|||
set s 0 |
|||
while {$d % 2 == 0} { |
|||
set d [expr {$d / 2}] |
|||
incr s |
|||
} |
|||
# LOOP |
|||
while {$k > 0} { |
|||
incr k -1 |
|||
set a [expr {2 + int(rand()*($n - 4))}] |
|||
set x [expr {($a ** $d) % $n}] |
|||
if {$x == 1 || $x == $n - 1} { |
|||
# do next LOOP |
|||
continue |
|||
} |
|||
set do_next_loop false |
|||
for {set r 1} {$r < $s} {incr r} { |
|||
set x [expr {($x ** 2) % $n}] |
|||
if {$x == 1} {return false} |
|||
if {$x == $n - 1} { |
|||
# do next LOOP |
|||
# Tcl can't directly control the outer loop from the inner loop |
|||
set do_next_loop true |
|||
break |
|||
} |
|||
} |
|||
if {$do_next_loop} continue |
|||
return false |
|||
} |
|||
return true |
|||
} |
|||
for {set i 1} {$i < 1000} {incr i} { |
|||
if {[miller_rabin $i 10]} { |
|||
puts $i |
|||
} |
|||
}</lang> |
|||
produces |
|||
<pre>1 |
|||
2 |
|||
3 |
|||
5 |
|||
7 |
|||
11 |
|||
... |
|||
977 |
|||
983 |
|||
991 |
|||
997</pre> |