Miller–Rabin primality test: Difference between revisions
Content added Content deleted
| Line 3,131: | Line 3,131: | ||
</lang> |
</lang> |
||
This is a |
=== This is a correct M-R test implementation for using bases > input. === |
||
=== It is deterministic for all integers < 2^64.=== |
|||
<lang nim> |
<lang nim> |
||
| Line 3,178: | Line 3,179: | ||
let (neg_one_mod, n) = (d, d) |
let (neg_one_mod, n) = (d, d) |
||
d = d shr countTrailingZeroBits(d) # suck out factors of 2 from d |
d = d shr countTrailingZeroBits(d) # suck out factors of 2 from d |
||
for b in witnesses: # do |
for b in witnesses: # do M-R test with each witness base |
||
if b.T mod num == 0: continue # **skip base if a multiple of input** |
if b.T mod num == 0: continue # **skip base if a multiple of input** |
||
var s = d |
var s = d |
||