Anonymous user
Miller–Rabin primality test: Difference between revisions
→Deterministic for integers < 3,317,044,064,679,887,385,961,981
Line 4,445:
return false if self.gcd(modp47) != 1 # eliminates 86.2% of all integers
# Choose witness bases for input; wits = [range, [wit_bases]] or nil
wits = WITNESS_RANGES.find { |range, wits| range > self }
witnesses = wits && wits[1] || primes
miller_rabin_test(witnesses)
Line 4,459:
next if (b % self) == 0 # **skip base if a multiple of input**
s = d
y = b.pow(d, self) # y = (b**d) mod self
until s == n || y == 1 || y == neg_one_mod
y = y.pow(2, self) # y = (y**2) mod self
s <<= 1
end
| |||