Miller–Rabin primality test: Difference between revisions

Content added Content deleted
Line 3,212: Line 3,212:
proc primemr*[T: SomeInteger](n: T): bool =
proc primemr*[T: SomeInteger](n: T): bool =
let primes = @[2u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
let primes = @[2u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
if n <= 47: return (n in primes)
if n <= primes[^1].T: return (n in primes) # for n <= primes.last
let modp47 = 614889782588491410u # => primes.product, largest < 2^64
let modp47 = 614889782588491410u # => primes.product, largest < 2^64
if gcd(n, modp47) != 1: return false # eliminates 86.2% of all integers
if gcd(n, modp47) != 1: return false # eliminates 86.2% of all integers