Miller–Rabin primality test: Difference between revisions

Content added Content deleted
(→‎{{header|Ruby}}: Update to 2.5+ and tidy)
Line 4,391: Line 4,391:


=={{header|Ruby}}==
=={{header|Ruby}}==
===Standard Probabilistic===
From 2.5 Ruby has fast modular exponentiation built in. For alternatives prior to 2.5 please see [[Modular_exponentiation#F.23]]
<lang ruby>
<lang ruby>
def mod_exp(n, e, mod)
fail ArgumentError, 'negative exponent' if e < 0
prod = 1
base = n % mod
until e.zero?
prod = (prod * base) % mod if e.odd?
e >>= 1
base = (base * base) % mod
end
prod
end

def miller_rabin_prime?(n, g)
def miller_rabin_prime?(n, g)
d = n - 1
d = n - 1
Line 4,413: Line 4,403:
g.times do
g.times do
a = 2 + rand(n - 4)
a = 2 + rand(n - 4)
x = mod_exp(a, d, n) # x = (a**d) % n
x = a.pow(d, n) # x = (a**d) % n
next if x == 1 || x == n - 1
next if x == 1 || x == n - 1
for r in (1..s - 1)
for r in (1..s - 1)
x = mod_exp(x, 2, n) # x = (x**2) % n
x = x.pow(2, n) # x = (x**2) % n
return false if x == 1
return false if x == 1
break if x == n - 1
break if x == n - 1
Line 4,439: Line 4,429:
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000)
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000)
</lang>
</lang>
===Deterministic for integers < 3,317,044,064,679,887,385,961,981===

⚫
It extends '''class Integer''' to make it simpler to use.
=== This is a correct M-R test implementation for using bases > input. ===
⚫
==== It monkey patches '''class Integer''' to make it simpler to use. ====
==== It is deterministic for all integers < 3_317_044_064_679_887_385_961_981.====
==== Increase 'primes' array members for more "confidence" past this value. ====

<lang ruby>
<lang ruby>
require "openssl" # for fast n.to_bn.mod_exp(exponent, modulus) method

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?
Line 4,461: Line 4,444:
miller_rabin_test(witnesses)
miller_rabin_test(witnesses)
end
end

private
private
# Returns true if +self+ passes Miller-Rabin Test with witness bases +b+
# Returns true if +self+ passes Miller-Rabin Test with witness bases +b+
Line 4,471: Line 4,454:
next if (b % self) == 0 # **skip base if a multiple of input**
next if (b % self) == 0 # **skip base if a multiple of input**
s = d
s = d
y = b.to_bn.mod_exp(d, self) # y = (b**d) mod self
y = b.pow(d, self) # y = (b**d) mod self
until s == n || y == 1 || y == neg_one_mod
until s == n || y == 1 || y == neg_one_mod
y = y.mod_exp(2, self) # y = (y**2) mod self
y = y.pow(2, self) # y = (y**2) mod self
s <<= 1
s <<= 1
end
end
Line 4,480: Line 4,463:
true
true
end
end

# Best known deterministic witnesses for given range and set of bases
# Best known deterministic witnesses for given range and set of bases
# https://miller-rabin.appspot.com/
# https://miller-rabin.appspot.com/
Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"