Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (→gmp version) |
(→{{header|Ruby}}: Update to 2.5+ and tidy) |
||
Line 4,391:
=={{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>
def miller_rabin_prime?(n, g)
d = n - 1
Line 4,413 ⟶ 4,403:
g.times do
a = 2 + rand(n - 4)
x =
next if x == 1 || x == n - 1
for r in (1..s - 1)
x =
return false if x == 1
break if x == n - 1
Line 4,439 ⟶ 4,429:
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000)
</lang>
===Deterministic for integers < 3,317,044,064,679,887,385,961,981===
▲==== It monkey patches '''class Integer''' to make it simpler to use. ====
<lang ruby>
class Integer
# Returns true if +self+ is a prime number, else returns false.
def primemr?
Line 4,461 ⟶ 4,444:
miller_rabin_test(witnesses)
end
private
# Returns true if +self+ passes Miller-Rabin Test with witness bases +b+
Line 4,471 ⟶ 4,454:
next if (b % self) == 0 # **skip base if a multiple of input**
s = d
y = b.
until s == n || y == 1 || y == neg_one_mod
y = y.
s <<= 1
end
Line 4,480 ⟶ 4,463:
true
end
# Best known deterministic witnesses for given range and set of bases
# https://miller-rabin.appspot.com/
|