Project

General

Profile

Feature #11578 ยป 0001-Add-Prime.probably_prime.patch

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