Miller–Rabin primality test: Difference between revisions
Content added Content deleted
(→{{header|Tcl}}: slightly less contorted code) |
|||
Line 406: | Line 406: | ||
if {$n <= 3} {return true} |
if {$n <= 3} {return true} |
||
if {$n % 2 == 0} {return false} |
if {$n % 2 == 0} {return false} |
||
# write n |
# write n - 1 as 2^s·d with d odd by factoring powers of 2 from n − 1 |
||
set d [expr {$n - 1}] |
set d [expr {$n - 1}] |
||
set s 0 |
set s 0 |
||
Line 414: | Line 414: | ||
incr s |
incr s |
||
} |
} |
||
# LOOP |
|||
while {$k > 0} { |
while {$k > 0} { |
||
incr k -1 |
incr k -1 |
||
set a [expr {2 + int(rand()*($n - 4))}] |
set a [expr {2 + int(rand()*($n - 4))}] |
||
set x [expr {($a ** $d) % $n}] |
set x [expr {($a ** $d) % $n}] |
||
if {$x == 1 || $x == $n - 1} |
if {$x == 1 || $x == $n - 1} continue |
||
# do next LOOP |
|||
continue |
|||
} |
|||
set do_next_loop false |
|||
for {set r 1} {$r < $s} {incr r} { |
for {set r 1} {$r < $s} {incr r} { |
||
set x [expr {($x ** 2) % $n}] |
set x [expr {($x ** 2) % $n}] |
||
if {$x == 1} {return false} |
if {$x == 1} {return false} |
||
if {$x == $n - 1} |
if {$x == $n - 1} break |
||
# 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 true |
return true |