Binary Paean

The Obligatory Miller-Rabin Implementation

At some point in a programmer’s life - perhaps several points - they are obligated to re-implement a primality test.

The Miller-Rabin test is a highly efficient way to determine if a given number is composite or prime. Here is my current implementation, in pure ruby.

module Primal
  attr :primal_s, :primal_d

  def prime?
    val = self.abs
    return true if val == 2
    return false if val % 2 == 0 || val == 1
    @s,@d = Primal::calc_sd(val- 1)
    Primal::witnesses(val).each do |wit|
      0.upto(@s-1) do |r|
        return false if ModMath.pow(wit,@d,val) == 1 && 
          ModMath.pow(wit,2*r*@d,val) == -1
      end
    end
   true 
  end

  class <<self
    #Return the minimal list of effective witnesses for 'sufficiently small'
    #Integers, otherwise derive the full set required for deterministic result.
    def witnesses(n)
     if n < 341550071728321
       [2, 3, 5, 7, 11, 13, 17]
      else
        calculate_witnesses(n)
      end
    end

    def calculate_witnesses(n)
      #Use the full list of possible witnesses for deterministic result
      max_val = [n-1,(2*(Math.log(n))**2).floor].min
      (2..max_val).to_a
    end

    def calc_sd(n)
     v = n; s = 0
     while v > 1 && (v & 0x1 == 0)
       s += 1
       v = v >> 1 
     end
     return s,v
    end
  end
end

#Fast exponentiation to a given modulo base
#Bogarted from http://snippets.dzone.com/posts/show/4636
module ModMath
   def ModMath.pow(base, power, mod)
     result = 1
     while power > 0
       result = (result * base) % mod if power & 1 == 1
       base = (base * base) % mod
       power >>= 1;
     end
     result
   end
end

#Inject the .prime? method into Integer 
  class Integer
    include Primal
  end

In the clear light of day I realized I don’t need the attribute accessors, and my @s and @d variables should be local. I’ll update once I’m near Vim again.