Anonymous user
Miller–Rabin primality test: Difference between revisions
→Deterministic for integers < 3,317,044,064,679,887,385,961,981
Line 4,489:
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
# Choose input witness bases
wits = WITNESS_RANGES.find { |range, wits| range > self }
witnesses = wits && wits[1] || primes
|