Test primes using the Miller-Rabin Method. See http://en.wikipedia.org/wiki/Miller-Rabin_primality_test for more details. For large prime numbers this is significantly faster than Ruby's default method.
The current standard Ruby Prime Generators are Generator23, EratosthenesSieve, and TrialDivision
The following code was used to compare Miller-Rabin with the existing Ruby Prime Generators:
require 'prime_miller_rabin'
require 'benchmark'
primes = load_primes() # Load primes from an external source
Prime::MillerRabin.speed_intercept
generators = {
MillerRabin: Prime::MillerRabin.new,
Generator23: Prime::Generator23.new,
Eratosthenes: Prime::EratosthenesGenerator.new,
TrialDivision: Prime::TrialDivisionGenerator.new
}
padding = ''
column_width = generators.keys.map(&:size).max
puts(generators.keys.map { |name| '%-*s' % [column_width, name] }.join('') + ' Number Tested')
time_limit = 120
primes.each_with_index do |number|
timings = generators.map { |name, generator| [name, Benchmark.measure { Prime.prime?(number, generator) }.total] }.to_h
puts timings.values.map { |x| '%-*.6f' % [column_width, x] }.push(padding).push(number).join(' ')
generators = generators.delete_if do |name, _|
if timings[name] > time_limit
puts "Removing #{name} as it is now exceeding #{time_limit / 60} minutes to determine primality."
padding += ' ' * (column_width + 1)
end
end
end
MillerRabin | Generator23 | Eratosthenes | TrialDivision | Number Tested |
---|---|---|---|---|
0.000 | 0.000 | 0.000 | 0.000 | 2 |
0.000 | 0.000 | 0.000 | 0.000 | 7 |
0.000 | 0.000 | 0.000 | 0.000 | 67 |
0.000 | 0.000 | 0.000 | 0.000 | 619 |
0.000 | 0.000 | 0.000 | 0.000 | 6197 |
0.000 | 0.000 | 0.000 | 0.000 | 61813 |
0.000 | 0.000 | 0.000 | 0.000 | 618041 |
0.000 | 0.000 | 0.000 | 0.000 | 6180341 |
0.000 | 0.000 | 0.000 | 0.000 | 61803419 |
0.000 | 0.000 | 0.015 | 0.016 | 618034003 |
0.000 | 0.015 | 0.016 | 0.141 | 6180339923 |
0.000 | 0.015 | 0.031 | 1.079 | 61803398903 |
0.015 | 0.063 | 0.047 | 6.500 | 618033988751 |
0.000 | 0.156 | 0.187 | 64.657 | 6180339887543 |
0.000 | 0.484 | 0.656 | 631.251 | 61803398875019 |
MillerRabin | Generator23 | Eratosthenes | Number Tested |
---|---|---|---|
0.000 | 1.578 | 1.905 | 618033988749911 |
0.000 | 4.828 | 5.938 | 6180339887498971 |
0.000 | 15.219 | 20.453 | 61803398874989489 |
0.000 | 51.344 | 78.500 | 618033988749894811 |
0.000 | 199.203 | 604.875 | 6180339887498948681 |
MillerRabin | Number Tested |
---|---|
0.000 | 61803398874989486159 |
0.000 | 618033988749894877249 |
0.000 | 6180339887498948771861 |
0.000 | 61803398874989479329793 |
0.000 | 618033988749894843629693 |
0.000 | 6180339887498948973166649 |
0.000 | 61803398874989485436698673 |
0.016 | 618033988749894820007248007 |
0.000 | 6180339887498948474950385857 |
0.000 | 61803398874989473754387579003 |
0.000 | 618033988749894825504806010893 |
0.000 | 6180339887498947551360618332249 |
0.000 | 61803398874989482269005624377351 |
0.000 | 618033988749894786661259224809529 |
0.000 | 6180339887498948010727780323950599 |
0.000 | 61803398874989484718963821666894041 |
0.000 | 618033988749894884083126364088041501 |
0.015 | 6180339887498948102961500692498350149 |
0.000 | 61803398874989478668431765490160893959 |
0.000 | 618033988749894805573783586380189794451 |
0.000 | 6180339887498948055737835863801897943079 |
0.016 | 61803398874989485393081637096535678255353 |
0.000 | 618033988749894834588003257131289987252251 |
0.000 | 6180339887498947881652517839295296785350671 |
0.000 | 61803398874989486244165414105234617248252037 |
0.016 | 618033988749894783213491626788008578938568879 |
0.000 | 6180339887498948782872866439052136911913091139 |
0.000 | 61803398874989490364029864846980172112537321529 |
0.000 | 618033988749894863075479441166460873230870642701 |
0.016 | 6180339887498948306236240753237881949152685850683 |
0.000 | 61803398874989488254659266067206448022023187726371 |
0.000 | 618033988749894861777405226532753966098246560383039 |
0.000 | 6180339887498948285467053319098571435030700533743709 |
0.015 | 61803398874989477537758550051322222735078764216058197 |
0.000 | 618033988749894860448177230747838093194439500102631463 |
0.000 | 6180339887498948264199405386539917468569787569258103079 |
0.016 | 61803398874989493531029795335430005513685313509163794507 |
0.000 | 618033988749894848198012021594053408512953632558975811599 |
0.000 | 6180339887498947959306404625379054205386139310393785319457 |
0.015 | 61803398874989483774453770978282381091808569225505635565881 |
0.000 | 618033988749894815443792511252200669382367419606694849675361 |
0.016 | 6180339887498947619220040347787051296966435652506272353222859 |
0.000 | 61803398874989487610181945125549561435952112121023814594199579 |
0.015 | 618033988749894876101819451255495614359521121210238145941995523 |
0.000 | 6180339887498948212955080513466361817213398943496249088445251857 |
0.016 | 61803398874989482129550805134663618172133989434962490884452515863 |
0.000 | 618033988749894751143429459463296107944467923968039965359763095659 |
0.016 | 6180339887498948446795342486410828729802972178101532233394458460333 |
0.000 | 61803398874989478481642718356729934335736646975120073823244888571933 |
0.015 | 618033988749894856652155661655839578904883367421943720360845238075493 |
0.016 | 6180339887498948949645441833030610378635590461796733108293232926654757 |
3.984 | 61803398874989480301481173134972953636273741716112229370497596164931657 |
0.016 | 618033988749894753974954423641286068895632548351228417905324051774046223 |
0.016 | 6180339887498948520546690390581730038298422859710161695046278715245855121 |
0.015 | 61803398874989478928365168519136536547194805389435200848107342688424034467 |
0.016 | 618033988749894789283651685191365365471948053894352008481073426884240343509 |
0.015 | 6180339887498948294571027916661222540210003624234170715361482714540612255771 |
0.016 | 61803398874989487766524411943583052027986313265829514720223808493784628461601 |
0.000 | 618033988749894800532217995004297294265682700282490226136494383363790190149697 |
0.016 | 6180339887498948416698319280344483481399122642162528507048910242032867738649237 |
0.015 | 61803398874989489103496864767062961278898774093676800018696699321068267432312833 |
0.000 | 618033988749894759394604061974146240391453136348727601568097742524293606434406857 |
0.016 | 6180339887498947804570623956855835799750586730828140653471168226341158572966019139 |
0.016 | 61803398874989483100696239659303319497571196124462157841676261489768925936587112561 |
0.015 | 618033988749894911886802398044952578976757222303513599328195882519406702676701872319 |
0.016 | 6180339887498948040470157294423934003086968742249909047796181923571167782622608752829 |
0.016 | 61803398874989482130138159641880286889558652991755453590739062278308316616857143476423 |
0.015 | 618033988749894793694396209256547719156563080809452726102954734101536945518474539565289 |
0.016 | 6180339887498948378655728287161559587390005993824156217900521559920108985586295718806271 |
0.016 | 61803398874989483786557282871615595873900059938241562179005215599201089855862957188055087 |
0.015 | 618033988749894837865572828716155958739000599382415621790052155992010898558629571880550497 |
0.016 | 6180339887498948830968576870427947960714166184011296269736399160078562264717483249716166887 |
0.016 | 61803398874989484691182980038148372620548380318615842282676970799517996414125332249876365411 |
0.015 | 618033988749894890333863264375057010044603181444123867803013957610391478937847325466187268189 |
0.016 | 6180339887498947977001918745221006711878151744937975851870262250979402473717801191356835561549 |
0.031 | 61803398874989483475366043046328320673053037727392809823342131810292073999820700166788504093107 |
0.016 | 618033988749894819932273008086810192513444296161875893014863280900928542947636248655004447015003 |
0.015 | 6180339887498948673607127596915238380081197557204429497142489999473035735094626582962223475327741 |
0.016 | 61803398874989482941796095840775292161237938807358930435474042471020354906000153058324802711846941 |
0.015 | 618033988749894799063759517380736188495787093956106388067133564520523529500432628412868570787086393 |
0.016 | 6180339887498948233471206702023495749890609292500927210972190526722675451480877501491721358521925753 |
0.015 | 61803398874989482334712067020234957498906092925009272109721905267226754514808775014917213585219257561 |
Add this line to your application's Gemfile:
gem 'prime_miller_rabin'
And then execute:
$ bundle
Or install it yourself as:
$ gem install prime_miller_rabin
require 'prime_miller_rabin'
# You now have access to Prime::MillerRabin
Prime.prime?(large_number, Prime::MillerRabin.new)
# Even when using the generator, Ruby's method for #prime? is slower than having Miller Rabin determine it directly.
# Miller Rabin can intercept the Prime.prime? function and call Miller Rabin directly when its generator is used.
# To accomplish this use:
Prime::MillerRabin.speed_intercept
# To use the speed intercept and have Miller Rabin be the default prime generator in all cases use:
Prime::MillerRabin.make_default