class Prime::MillerRabin

Constants

VERSION

Attributes

last_prime[RW]

Public Class Methods

make_default() click to toggle source
# File lib/prime_miller_rabin.rb, line 22
  def self.make_default
    if RUBY_VERSION >= "2.0"
      Prime.send(:prepend, Prime::MillerRabin::Default::Prime, Prime::MillerRabin::PrimeIntercept)
      Integer.send(:prepend, Prime::MillerRabin::Default::Integer)
    else
      Prime.class_eval <<-PRIME_DEFAULT_EVAL, __FILE__, __LINE__ + 1
        # Change the default generator used to be MillerRabin
        def prime_with_mr_default?(value, generator = ::Prime::MillerRabin.new)
          generator.instance_of?(Prime::MillerRabin) ? generator.prime?(value) : prime_without_mr_default?(value, generator)
        end

        def prime_division_with_mr_default?(value, generator = ::Prime::MillerRabin.new)
          prime_division_without_mr_default?(value, generator)
        end

        alias_method "prime_without_mr_default?", "prime?"
        alias_method "prime?", "prime_with_mr_default?"

        alias_method "prime_division_without_mr_default?", "prime_division"
        alias_method "prime_division", "prime_division_with_mr_default?"
      PRIME_DEFAULT_EVAL

      Integer.class_eval <<-INTEGER_DEFAULT_EVAL, __FILE__, __LINE__ + 1

        def prime_division_with_mr_default(generator = ::Prime::MillerRabin.new)
          prime_division_without_mr_default(generator)
        end

        alias_method "prime_division_with_mr_default?", "prime_division"
        alias_method "prime_division", "prime_division_with_mr_default?"
      INTEGER_DEFAULT_EVAL

    end
  end
speed_intercept() click to toggle source
# File lib/prime_miller_rabin.rb, line 7
  def self.speed_intercept
    if RUBY_VERSION >= "2.0"
      Prime.send(:prepend, Prime::MillerRabin::PrimeIntercept)
    else
      Prime.class_eval <<-INTERCEPT_EVAL, __FILE__, __LINE__ + 1
        def prime_with_intercept?(value, *args)
          args.first.instance_of?(Prime::MillerRabin) ? args.first.prime?(value) : prime_without_intercept?(value, *args)
        end

        alias_method "prime_without_intercept?", "prime?"
        alias_method "prime?", "prime_with_intercept?"
      INTERCEPT_EVAL
    end
  end

Public Instance Methods

prime?(x) click to toggle source
# File lib/prime_miller_rabin.rb, line 65
def prime?(x)
  miller_rabin(x)
end
rewind() click to toggle source
# File lib/prime_miller_rabin.rb, line 61
def rewind()
  self.last_prime = nil
end
succ() click to toggle source
# File lib/prime_miller_rabin.rb, line 57
def succ()
  self.last_prime = next_prime(last_prime || 1)
end

Private Instance Methods

likely_prime?(a, n) click to toggle source
# File lib/prime_miller_rabin.rb, line 73
def likely_prime?(a, n)
  d = n - 1
  s = 0
  while d % 2 == 0 do
    d >>= 1
    s += 1
  end

  b = 1
  while d > 0
    u = d % 2
    t = d / 2
    b = (b * a) % n if u == 1
    a = a**2 % n
    d = t
  end

  if b == 1
    true
  else
    s.times do |i|
      return true if b == n - 1
      b = (b * b) % n
    end
    (b == n - 1)
  end
end
miller_rabin(n) click to toggle source
# File lib/prime_miller_rabin.rb, line 101
def miller_rabin(n)
  if n.abs < 2
    false
  else
    likely_prime = true
    # 26 Yields a probability of prime at 99.99999999999998% so lets kick it up a notch.
    27.times do |i|
      begin
        a = rand(n)
      end while a == 0
      likely_prime = likely_prime?(a, n)
      break unless likely_prime
    end
    likely_prime
  end
end
next_prime(x) click to toggle source
# File lib/prime_miller_rabin.rb, line 118
def next_prime(x)
  if x < 2
    2
  elsif x < 3
    3
  elsif x < 5
    5
  else
    x += (x.even? ? 1 : (x % 10 == 3 ? 4 : 2 ))
    x += (x % 10 == 3 ? 4 : 2 ) until x.prime?
    x
  end
end