### Profile

View differences:

lib/prime.rb
145 145
`    end`
146 146
`  end`
147 147

148
`  # Miller-Rabin Test to check if a given number is probably prime`
149
`  #  or composite`
150
`  # Returns true if n is probably prime, false if n is composite`
151
`  # == Parameters`
152
`  #`
153
`  #  +n+:: an arbitary integer to be checked`
154
`  #  +k+:: optional, A parameter that determines the accuracy`
155
`  #                  of the test`
156
`  #  References: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test`
157
`  #              http://rosettacode.org/wiki/Miller-Rabin_primality_test#Ruby`
158
`  def probably_prime?(n, k = 30)`
159
`    raise ArgumentError, 'n should be >= 3' if n < 3`
160
`    d = n - 1`
161
`    r = 0`
162
`    while d & 1 == 0 do`
163
`      d = d / 2`
164
`      r += 1`
165
`    end`
166

167
`    k.times do`
168
`      a = 2 + rand(n - 4)`
169
`      x = mod_exp(a, d, n)`
170
`      next if x == 1 || x == (n - 1)`
171

172
`      (r - 1).times do`
173
`        x = mod_exp(x, 2, n)`
174
`        return false if x == 1`
175
`        break if x == (n - 1)`
176
`      end`
177
`      return false if x != (n - 1)`
178
`    end`
179

180
`    true`
181
`  end`
182

183

148 184
`  # Re-composes a prime factorization and returns the product.`
149 185
`  #`
150 186
`  # == Parameters`
......
453 489
`      @max_checked = segment_max`
454 490
`    end`
455 491
`  end`
492

493
`  private`
494

495
`  # returns (base ^ exp) % n`
496
`  # modular exponentiation by squaring`
497
`  # https://en.wikipedia.org/wiki/Modular_exponentiation`
498
`  def mod_exp(base, exp, n)`
499
`    product = 1`
500
`    base = base % n`
501
`    while exp != 0 do`
502
`      product = (product * base) % n if exp & 1 == 1`
503
`      exp = exp >> 1`
504
`      base = (base * base) % n`
505
`    end`
506

507
`    product`
508
`  end`
456 509
`end`
test/test_prime.rb
190 190

191 191
`    assert_not_include Prime.each(7*37).to_a, 7*37, "[ruby-dev:39465]"`
192 192
`  end`
193

194
`  def test_probably_prime`
195
`    assert_equal Prime.probably_prime?(961_748_941), true`
196
`    assert_equal Prime.probably_prime?(4547337172376300111955330758342147474062293202868155909489), true`
197
`    assert_raise ArgumentError do`
198
`      Prime.probably_prime?(2)`
199
`    end`
200
`    PRIMES[1, PRIMES.length - 1].each do |prime|`
201
`      assert_equal Prime.probably_prime?(prime), true`
202
`    end`
203

204
`    assert_equal Prime.probably_prime?(314159 * (10 ** 765) + 951413), true`
205
`    assert_equal Prime.probably_prime?(1749343240116807117649823543576480140353607282475249), true`
206
`    assert_equal Prime.probably_prime?(999999999999999999999999999999999841), true`
207
`    assert_equal Prime.probably_prime?(25262728293031323334353637383940414243444546474849), true`
208
`    assert_equal Prime.probably_prime?(33452526613163807108170062053440751665152000000001), true`
209
`    assert_equal Prime.probably_prime?(1808422353177349564546512035512530001279481259854248860454348989451026887), true`
210
`    assert_equal Prime.probably_prime?(13579111_3151719313_3353739515_3555759717_3757779919_3959799111_1131151171_1913113313_5137139151_1531551571_5917117317_5177179191_1931951971_9931131331_5317319331_3333353373_3935135335_5357359371_3733753773_7939139339_5397399511_5135155175_1953153353_5537539551_5535555575_5957157357_5577579591_5935955975_9971171371_5717719731_7337357377_3975175375_5757759771, 1000), true`
211
`    assert_equal Prime.probably_prime?(98765432101456789), true`
212
`    assert_equal Prime.probably_prime?(99194853094755497), true`
213
`    assert_equal Prime.probably_prime?((10 ** 100) - 1), false`
214
`    assert_equal Prime.probably_prime?(2 ** 256), false`
215
`    assert_equal Prime.probably_prime?(9 ** 512), false`
216
`    assert_equal Prime.probably_prime?(13579111_3151719313_3353739515_3555759717_3757779919_3959799111_1131151171_1913113313_5137139151_1531551571_5917117317_5177179191_1931951971_9931131331_5317319331_3333353373_3935135335_5357359371_3733753773_7939139339_5397399511_5135155175_1953153353_5537539551_5535555575_5957157357_5577579591_5935955975_9971171371_5717719731_7337357377_3975175375_5757759770, 1000), false`
217
`  end`
193 218
`end`