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:

Prime::MillerRabin.speed_intercept

miller_rabin = Prime::MillerRabin.new
generator23 = Prime::Generator23.new
eratosthenes = Prime::EratosthenesGenerator.new
trial_division = Prime::TrialDivisionGenerator.new

generators = [miller_rabin, generator23, eratosthenes, trial_division]
generator_names = ['MillerRabin', 'Generator23', 'Eratosthenes', 'TrialDivision']

puts(("%-15s" * generator_names.size) % generator_names + "    Number Tested")
primes.each_with_index do |number|
  remove = []
  timings = []
  generators.each_with_index do |generator, j|
    if generator
      name = generator_names[j]
      benchmark = Benchmark.measure { Prime.prime?(number, generator) }
      if benchmark.total > 120
        puts "Removing #{name} as it is now exceeding 2 minutes to determine primality"
        remove << generator
      end
      timings << benchmark.total
    else
      timings << nil
    end
  end
  timings.map! { |x| x ? '%-15.6f' % [x] : '%15s' % [' '] }
  timings << number
  puts timings.join(' ')
  generators.map! { |x| remove.include?(x) ? nil : x }
end

The results (formatted for readability):

MillerRabin    Generator23    Eratosthenes   TrialDivision      Number Tested
0.000000        0.000000        0.000000        0.000000        2
0.000000        0.000000        0.000000        0.000000        7
0.000000        0.000000        0.000000        0.000000        67
0.000000        0.000000        0.000000        0.000000        619
0.000000        0.000000        0.000000        0.000000        6197
0.000000        0.000000        0.000000        0.000000        61813
0.000000        0.000000        0.000000        0.000000        618041
0.000000        0.000000        0.010000        0.000000        6180341
0.000000        0.000000        0.000000        0.010000        61803419
0.000000        0.000000        0.020000        0.030000        618034003
0.000000        0.010000        0.050000        0.120000        6180339923
0.000000        0.040000        0.220000        1.690000        61803398903
0.000000        0.140000        0.990000        13.080000       618033988751
0.010000        0.390000        4.110000        119.750000      6180339887543
Removing TrialDivision as it is now exceeding 2 minutes to determine primality
0.000000        1.820000        30.460000       1081.650000     61803398875019
Removing Eratosthenes as it is now exceeding 2 minutes to determine primality
0.000000        7.180000        139.250000                      618033988749911
0.010000        16.990000                                       6180339887498971
0.000000        53.850000                                       61803398874989489
Removing Generator23 as it is now exceeding 2 minutes to determine primality
0.010000        170.560000                                      618033988749894811

MillerRabin Number Tested
0.000000  6180339887498948681
0.000000  61803398874989486159
0.000000  618033988749894877249
0.000000  6180339887498948771861
0.020000  61803398874989479329793
0.000000  618033988749894843629693
0.010000  6180339887498948973166649
0.000000  61803398874989485436698673
0.000000  618033988749894820007248007
0.020000  6180339887498948474950385857
0.000000  61803398874989473754387579003
0.000000  618033988749894825504806010893
0.010000  6180339887498947551360618332249
0.020000  61803398874989482269005624377351
0.000000  618033988749894786661259224809529
0.010000  6180339887498948010727780323950599
0.020000  61803398874989484718963821666894041
0.000000  618033988749894884083126364088041501
0.010000  6180339887498948102961500692498350149
0.020000  61803398874989478668431765490160893959
0.000000  618033988749894805573783586380189794451
0.010000  6180339887498948055737835863801897943079
0.020000  61803398874989485393081637096535678255353
0.010000  618033988749894834588003257131289987252251
0.000000  6180339887498947881652517839295296785350671
0.020000  61803398874989486244165414105234617248252037
0.010000  618033988749894783213491626788008578938568879
0.020000  6180339887498948782872866439052136911913091139
0.010000  61803398874989490364029864846980172112537321529
0.020000  618033988749894863075479441166460873230870642701
0.010000  6180339887498948306236240753237881949152685850683
0.020000  61803398874989488254659266067206448022023187726371
0.010000  618033988749894861777405226532753966098246560383039
0.020000  6180339887498948285467053319098571435030700533743709
0.010000  61803398874989477537758550051322222735078764216058197
0.030000  618033988749894860448177230747838093194439500102631463
0.000000  6180339887498948264199405386539917468569787569258103079
0.030000  61803398874989493531029795335430005513685313509163794507
0.010000  618033988749894848198012021594053408512953632558975811599
0.020000  6180339887498947959306404625379054205386139310393785319457
0.010000  61803398874989483774453770978282381091808569225505635565881
0.030000  618033988749894815443792511252200669382367419606694849675361
0.020000  6180339887498947619220040347787051296966435652506272353222859
0.010000  61803398874989487610181945125549561435952112121023814594199579
0.030000  618033988749894876101819451255495614359521121210238145941995523
0.030000  6180339887498948212955080513466361817213398943496249088445251857
0.010000  61803398874989482129550805134663618172133989434962490884452515863
0.030000  618033988749894751143429459463296107944467923968039965359763095659
0.020000  6180339887498948446795342486410828729802972178101532233394458460333
0.020000  61803398874989478481642718356729934335736646975120073823244888571933
0.030000  618033988749894856652155661655839578904883367421943720360845238075493
0.030000  6180339887498948949645441833030610378635590461796733108293232926654757
0.010000  61803398874989480301481173134972953636273741716112229370497596164931657
0.030000  618033988749894753974954423641286068895632548351228417905324051774046223
0.030000  6180339887498948520546690390581730038298422859710161695046278715245855121
0.030000  61803398874989478928365168519136536547194805389435200848107342688424034467
0.030000  618033988749894789283651685191365365471948053894352008481073426884240343509
0.030000  6180339887498948294571027916661222540210003624234170715361482714540612255771
0.030000  61803398874989487766524411943583052027986313265829514720223808493784628461601
0.030000  618033988749894800532217995004297294265682700282490226136494383363790190149697
0.030000  6180339887498948416698319280344483481399122642162528507048910242032867738649237
0.020000  61803398874989489103496864767062961278898774093676800018696699321068267432312833
0.030000  618033988749894759394604061974146240391453136348727601568097742524293606434406857
0.030000  6180339887498947804570623956855835799750586730828140653471168226341158572966019139
0.030000  61803398874989483100696239659303319497571196124462157841676261489768925936587112561
0.040000  618033988749894911886802398044952578976757222303513599328195882519406702676701872319
0.030000  6180339887498948040470157294423934003086968742249909047796181923571167782622608752829
0.040000  61803398874989482130138159641880286889558652991755453590739062278308316616857143476423
0.040000  618033988749894793694396209256547719156563080809452726102954734101536945518474539565289
0.040000  6180339887498948378655728287161559587390005993824156217900521559920108985586295718806271
0.040000  61803398874989483786557282871615595873900059938241562179005215599201089855862957188055087
0.030000  618033988749894837865572828716155958739000599382415621790052155992010898558629571880550497
0.020000  6180339887498948830968576870427947960714166184011296269736399160078562264717483249716166887
0.040000  61803398874989484691182980038148372620548380318615842282676970799517996414125332249876365411
0.030000  618033988749894890333863264375057010044603181444123867803013957610391478937847325466187268189
0.040000  6180339887498947977001918745221006711878151744937975851870262250979402473717801191356835561549
0.050000  61803398874989483475366043046328320673053037727392809823342131810292073999820700166788504093107
0.040000  618033988749894819932273008086810192513444296161875893014863280900928542947636248655004447015003
0.030000  6180339887498948673607127596915238380081197557204429497142489999473035735094626582962223475327741
0.040000  61803398874989482941796095840775292161237938807358930435474042471020354906000153058324802711846941
0.030000  618033988749894799063759517380736188495787093956106388067133564520523529500432628412868570787086393
0.040000  6180339887498948233471206702023495749890609292500927210972190526722675451480877501491721358521925753

Larger numbers

For primes nearing a googol (10**100) it is still subsecond. Starting at a google - 3 the following was used for benchmarking,

Benchmark.bm do |x|
  (1..50).each do |z|
    exponent = "#{z}00".to_i
    number = 10**exponent - 3
    x.report("10**#{exponent} - 3") { number.prime? }
  end
end

Results (formatted for readability)

              user       system     total       real
10**100 - 3   0.000000   0.000000   0.000000 (  0.000873)
10**200 - 3   0.000000   0.000000   0.000000 (  0.003954)
10**300 - 3   0.010000   0.000000   0.010000 (  0.008990)
10**400 - 3   0.020000   0.000000   0.020000 (  0.019595)
10**500 - 3   0.030000   0.000000   0.030000 (  0.030311)
10**600 - 3   0.050000   0.000000   0.050000 (  0.045907)
10**700 - 3   0.080000   0.010000   0.090000 (  0.086039)
10**800 - 3   0.120000   0.000000   0.120000 (  0.120604)
10**900 - 3   0.140000   0.000000   0.140000 (  0.137074)
10**1000 - 3  0.190000   0.000000   0.190000 (  0.197226)
10**1100 - 3  0.270000   0.010000   0.280000 (  0.267312)
10**1200 - 3  0.340000   0.000000   0.340000 (  0.344282)
10**1300 - 3  0.370000   0.000000   0.370000 (  0.376330)
10**1400 - 3  0.520000   0.010000   0.530000 (  0.530934)
10**1500 - 3  0.610000   0.010000   0.620000 (  0.622023)
10**1600 - 3  0.810000   0.010000   0.820000 (  0.817583)
10**1700 - 3  0.910000   0.010000   0.920000 (  0.917380)
10**1800 - 3  1.050000   0.010000   1.060000 (  1.071910)
10**1900 - 3  1.180000   0.020000   1.200000 (  1.189116)
10**2000 - 3  1.410000   0.020000   1.430000 (  1.438527)
10**2100 - 3  1.480000   0.020000   1.500000 (  1.499630)
10**2200 - 3  1.820000   0.030000   1.850000 (  1.838164)
10**2300 - 3  2.000000   0.030000   2.030000 (  2.026655)
10**2400 - 3  1.970000   0.020000   1.990000 (  1.997051)
10**2500 - 3  2.580000   0.040000   2.620000 (  2.616159)
10**2600 - 3  3.060000   0.050000   3.110000 (  3.110208)
10**2700 - 3  2.900000   0.050000   2.950000 (  2.950306)
10**2800 - 3  2.900000   0.050000   2.950000 (  2.945470)
10**2900 - 3  3.310000   0.050000   3.360000 (  3.360690)
10**3000 - 3  3.700000   0.070000   3.770000 (  3.765682)
10**3100 - 3  4.610000   0.070000   4.680000 (  4.680919)
10**3200 - 3  5.530000   0.080000   5.610000 (  5.615243)
10**3300 - 3  4.770000   0.090000   4.860000 (  4.860779)
10**3400 - 3  5.190000   0.090000   5.280000 (  5.278715)
10**3500 - 3  5.800000   0.100000   5.900000 (  5.891275)
10**3600 - 3  6.310000   0.110000   6.420000 (  6.417548)
10**3700 - 3  8.450000   0.070000   8.520000 (  8.510452)
10**3800 - 3  8.830000   0.070000   8.900000 (  8.901605)
10**3900 - 3  8.040000   0.080000   8.120000 (  8.114340)
10**4000 - 3 10.030000   0.050000  10.080000 ( 10.087971)
10**4100 - 3  8.730000   0.060000   8.790000 (  8.782747)
10**4200 - 3 11.550000   0.070000  11.620000 ( 11.607290)
10**4300 - 3 10.810000   0.100000  10.910000 ( 10.913006)
10**4400 - 3 12.380000   0.180000  12.560000 ( 12.552739)
10**4500 - 3 12.580000   0.180000  12.760000 ( 12.753963)
10**4600 - 3 13.130000   0.190000  13.320000 ( 13.311686)
10**4700 - 3 14.380000   0.190000  14.570000 ( 14.560988)
10**4800 - 3 13.680000   0.220000  13.900000 ( 13.895690)
10**4900 - 3 15.800000   0.220000  16.020000 ( 16.017528)
10**5000 - 3 15.290000   0.230000  15.520000 ( 15.513277)

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

Contributing

  1. Fork it
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create new Pull Request