Anonymous user
Miller–Rabin primality test: Difference between revisions
→{{header|Ruby}}
m (→{{header|Rust}}: Added two test cases (with integers as input).) |
|||
Line 4,220:
puts miller_rabin_prime?(153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599,1000)
puts miller_rabin_prime?(103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041,1000)
</lang>
This version 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 'prime' array members for more "confidence" past this value.
<lang ruby>
require "openssl" # for fast n.to_bn.mod_exp(exponent, modulus) method
class Integer
# Returns true if +self+ is a prime number, else returns false.
def primemr?
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
return primes.include? self if self <= primes.last
modp47 = 614889782588491410 # => primes.reduce(:*), largest < 2^64
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)
end
private
# Returns true if +self+ passes Miller-Rabin Test with witness bases +b+
def miller_rabin_test(witnesses) # use witness list to test with
neg_one_mod = n = d = self - 1 # these are even as 'self' always odd
d >>= 4 while (d & 0xf) == 0 # suck out factors of 2
(d >>= (d & 3)^2; d >>= (d & 1)^1) if d.even? # 4 bits at a time
witnesses.each do |b| # loop over witness bases
next if (b % self) == 0 # **skip base if a multiple of input**
s = d
y = b.to_bn.mod_exp(d, self) # y = (b**d) mod self
until s == n || y == 1 || y == neg_one_mod
y = y.mod_exp(2, self) # y = (y**2) mod self
s <<= 1
end
return false unless y == neg_one_mod || s.odd?
end
true
end
# Best known deterministic witnesses for given range and set of bases
# https://miller-rabin.appspot.com/
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
WITNESS_RANGES = {
341_531 => [9345883071009581737],
1_050_535_501 => [336781006125, 9639812373923155],
350_269_456_337 => [4230279247111683200, 14694767155120705706, 16641139526367750375],
55_245_642_489_451 => [2, 141889084524735, 1199124725622454117, 11096072698276303650],
7_999_252_175_582_851 => [2, 4130806001517, 149795463772692060, 186635894390467037,
3967304179347715805],
585_226_005_592_931_977 => [2, 123635709730000, 9233062284813009, 43835965440333360,
761179012939631437, 1263739024124850375],
18_446_744_073_709_551_615 => [2, 325, 9375, 28178, 450775, 9780504, 1795265022],
318_665_857_834_031_151_167_461 => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37],
3_317_044_064_679_887_385_961_981 => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
}
end
# 58 digit prime
n = 4547337172376300111955330758342147474062293202868155909489
puts "\n number = #{n} is prime? is #{n.primemr?}"
# 58 digit non-prime
n = 4547337172376300111955330758342147474062293202868155909393
puts "\n number = #{n} is prime? is #{n.primemr?}"
# 81 digit prime
n = 100000000000000000000000000000000000000000000000000000000000000000000000001309503
puts "\n number = #{n} is prime? is #{n.primemr?}"
# 81 digit non-prime
n = 100000000000000000000000000000000000000000000000000000000000000000000000001309509
puts "\n number = #{n} is prime? is #{n.primemr?}"
# 308 digit prime
n = 9436639673033417338310735304941495952152881531054818703016593622957896020952342180891245979532903520351028457618716007638664370044121654773291425057893426189151082714026704359200722516079834891363947256471505544520151246135935948879542787553023100#1298552452230535485049737222714000227878890892901228389026881
puts "\n number = #{n} is prime? is #{n.primemr?}"
n = 138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401
puts "\n number = #{n} is prime? is #{n.primemr?}"
n = 123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841
puts "\n number = #{n} is prime? is #{n.primemr?}"
n = 119432521682023078841121052226157857003721669633106050345198988740042219728400958282159638484144822421840470442893056822510584029066504295892189315912923804894933736660559950053226576719285711831138657839435060908151231090715952576998400120335346005544083959311246562842277496260598128781581003807229557518839
puts "\n number = #{n} is prime? is #{n.primemr?}"
n = 132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731
puts "\n number = #{n} is prime? is #{n.primemr?}"
n = 153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599
puts "\n number = #{n} is prime? is #{n.primemr?}"
n = 103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041
puts "\n number = #{n} is prime? is #{n.primemr?}"
n = 94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881
puts "\n number = #{n} is prime? is #{n.primemr?}"
</lang>
| |||