Miller–Rabin primality test: Difference between revisions
Content added Content deleted
Line 1,031: | Line 1,031: | ||
# Returns true if +self+ is a prime number, else returns false. |
# Returns true if +self+ is a prime number, else returns false. |
||
def primemr? |
def primemr? |
||
raise ArgumentError.new "Input must be non-negative integer" if self < 0 |
|||
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47} |
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47} |
||
return primes.includes? self if self <= primes.last |
return primes.includes? self if self <= primes.last |
||
modp47 = 614_889_782_588_491_410 |
modp47 = 614_889_782_588_491_410.to_big_i # => primes.product, largest < 2^64 |
||
return false if modp47.gcd(self.to_big_i) != 1 # eliminates 86.2% of all integers |
return false if modp47.gcd(self.to_big_i) != 1 # eliminates 86.2% of all integers |
||
n = typeof(self).new(self) |
|||
# wits = [range, [wit_prms]] or nil |
# wits = [range, [wit_prms]] or nil |
||
wits = WITNESS_RANGES.find {|range, wits| range > |
wits = WITNESS_RANGES.find {|range, wits| range > self} |
||
witnesses = wits && wits[1] || primes |
witnesses = wits && wits[1] || primes |
||
miller_rabin_test(witnesses) |
miller_rabin_test(witnesses) |
||
Line 1,073: | Line 1,073: | ||
# Best known deterministic witnesses for given range and set of bases |
# Best known deterministic witnesses for given range and set of bases |
||
# https://miller-rabin.appspot.com/ |
# https://miller-rabin.appspot.com/ |
||
# https://en.wikipedia.org/wiki/Miller%E2%80% |
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test |
||
private WITNESS_RANGES = { |
private WITNESS_RANGES = { |
||
341_531 => {9345883071009581737}, |
341_531 => {9345883071009581737}, |