Miller–Rabin primality test: Difference between revisions
Content added Content deleted
| Line 4,489: | Line 4,489: | ||
modp47 = 614_889_782_588_491_410 # => primes.reduce(:*), largest < 2^64 |
modp47 = 614_889_782_588_491_410 # => primes.reduce(:*), largest < 2^64 |
||
return false if self.gcd(modp47) != 1 # eliminates 86.2% of all integers |
return false if self.gcd(modp47) != 1 # eliminates 86.2% of all integers |
||
# Choose witness bases |
# Choose input witness bases: wits = [range, [wit_bases]] or nil |
||
wits = WITNESS_RANGES.find { |range, wits| range > self } |
wits = WITNESS_RANGES.find { |range, wits| range > self } |
||
witnesses = wits && wits[1] || primes |
witnesses = wits && wits[1] || primes |
||