class Integer

Public Instance Methods

mrd_prime?() click to toggle source

Returns true if self is a prime number, else returns false.

en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test oeis.org/A014233/list

“if n < 3,317,044,064,679,887,385,961,981, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41. and the result will be deterministic.”

# File lib/mrd_prime.rb, line 15
def mrd_prime?

  return false if self < 2
  return true  if self < 4
  return false if self.even?

  prime_and_max = {
    2  =>  8321,      # 2047.  Strong pseudoprimes to base 2, [ 2047(=23x89), 3277(=29x113), 4033(=37x109), 4681(=31x151), 8321(=53x157) ] ~ 4681 is divided by a small prime number.
    3  =>  1373653,
    5  =>  25326001,
    7  =>  3215031751,
    11  =>  2152302898747,
    13  =>  3474749660383,
    17  =>  341550071728321,
    19  =>  341550071728321,
    23  =>  3825123056546413051,
    29  =>  3825123056546413051,
    31  =>  3825123056546413051,
    37  =>  318665857834031151167461,
    41  =>  3317044064679887385961981,
  }
  
  last_p = 1
  prime_and_max.each do |p,m|
    return true if self == p
    return false if self % p == 0
    last_p = p
  end
  return true if self < last_p * last_p

  p_1 = self - 1

  d = p_1
  while d.even?
    d >>= 1
  end

  prime_and_max.each do |a,m|
    x = a.pow( d, self )

    if x == 1
      return true if self < m
      next
    end

    td = d
    while td != p_1 && x != p_1
      x = x.pow( 2, self )
      td <<= 1
    end

    if td == p_1
      return false
    else
      return true if x == p_1 && self < m
    end

  end

  # OpenSSL fallback
  # return true
  return OpenSSL::BN.new( self ).prime?
end