PrimeMillerRabin
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.
Benchmarks
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
The results (formatted for readability):
| 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 |
Removing TrialDivision as it is now exceeding 2 minutes to determine primality
| 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 |
Removing Generator23 as it is now exceeding 2 minutes to determine primality
Removing Eratosthenes as it is now exceeding 2 minutes to determine primality
| 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 |
Installation
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
Usage
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