Miller–Rabin primality test: Difference between revisions
Content added Content deleted
| Line 1,070: | Line 1,070: | ||
require "big" |
require "big" |
||
require "random" |
|||
module Primes |
module Primes |
||
| Line 1,075: | Line 1,076: | ||
# 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?(k = 10) |
||
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 |
||
| Line 1,082: | Line 1,083: | ||
# Choose input witness bases: wits = [range, [wit_bases]] or nil |
# 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] || |
witnesses = wits && wits[1] || k.times.map{ 2 + rand(self - 4) } |
||
miller_rabin_test(witnesses) |
miller_rabin_test(witnesses) |
||
end |
end |
||