Miller–Rabin primality test: Difference between revisions
Content added Content deleted
Line 4,485: | Line 4,485: | ||
class Integer |
class Integer |
||
# 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.include? self if self <= primes.last |
return primes.include? self if self <= primes.last |
||
Line 4,492: | Line 4,492: | ||
# 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(n - 4) } |
||
miller_rabin_test(witnesses) |
miller_rabin_test(witnesses) |
||
end |
end |