Miller–Rabin primality test: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
| Line 1,045: | Line 1,045: | ||
private def miller_rabin_test(witnesses) # list of witnesses for testing |
private def miller_rabin_test(witnesses) # list of witnesses for testing |
||
neg_one_mod = n = d = self - 1 # these are even as self is always odd |
neg_one_mod = n = d = self - 1 # these are even as self is always odd |
||
d >>= d.trailing_zeros_count # shift out factors of 2 to make d odd |
|||
(d >>= (d & 3)^2; d >>= (d & 1)^1) if d.even? # 4 bits at a time |
|||
witnesses.each do |b| # do M-R test with each witness base |
witnesses.each do |b| # do M-R test with each witness base |
||
next if (b % self) == 0 # **skip base if a multiple of input** |
next if (b % self) == 0 # **skip base if a multiple of input** |
||