Module: FasterPrime::PrimalityTest

Defined in:
lib/faster_prime/primality_test.rb

Defined Under Namespace

Classes: APRCL

Constant Summary collapse

DEFAULT_RANDOM = 
Random.new
DETERMINISTIC_MR_TEST_TABLE =

These numbers are taken from:

http://code.google.com/p/sympy/
http://primes.utm.edu/prove/prove2_3.html

[
  [          1_373_653, [2, 3]],
  [        170_584_961, [350, 3_958_281_543]],
  [      4_759_123_141, [2, 7, 61]],
  [     75_792_980_677, [2, 379_215, 457_083_754]],
  [  1_000_000_000_000, [2, 13, 23, 1_662_803]],
  [  2_152_302_898_747, [2, 3, 5, 7, 11]],
  [  3_474_749_660_383, [2, 3, 5, 7, 11, 13]],
  [341_550_071_728_321, [2, 3, 5, 7, 11, 13, 17]],
]

Class Method Summary collapse

Class Method Details

.prime?(n, random = DEFAULT_RANDOM) ⇒ Boolean

Returns:

  • (Boolean) 


9
10
11
12
13
 
# File 'lib/faster_prime/primality_test.rb', line 9

def prime?(n, random = DEFAULT_RANDOM)
  r = probable_prime?(n, random)
  return r if r != nil
  return APRCL.prime?(n)
end

.probable_prime?(n, random = Random.new) ⇒ Boolean

Miller-Rabin primality test Returns true for a prime, false for a composite, nil if unknown.

Returns:

  • (Boolean) 


17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/faster_prime/primality_test.rb', line 17

def probable_prime?(n, random = Random.new)
  return n >= 2 if n <= 3
  return true  if n == 2 || n == 3
  return true if n == 5
  return false unless 30.gcd(n) == 1
  return SMALL_PRIME_TABLE[n / 2] if n / 2 < SMALL_PRIME_TABLE.size
  m = n % 6
  return false if m != 1 && m != 5

  list = DETERMINISTIC_MR_TEST_TABLE.find {|t,| n < t }
  if list
    ret = true
    list = list.last
  else
    ret = nil
    list = (1..20).map { random.rand(n - 2) + 1 }
  end

  d, s = n - 1, 0
  while d.even?
    d >>= 1
    s += 1
  end
  list.each do |a|
    y = Utils.mod_pow(a, d, n)
    if y != 1
      f = s.times do
        break if y == n - 1
        y = (y * y) % n
      end
      return false if f
    end
  end

  ret
end