lib/secretsharing/shamir.rb
def miller_rabin_prime?(n, g = 1000)
      return false if n == 1
      return true if n == 2

      d = n - 1
      s = 0

      while d.even?
        d /= 2
        s += 1
      end

      g.times do
        a = 2 + rand(n - 4)
        x = mod_exp(a, d, n) # x = (a**d) % n
        next if x == 1 || x == n - 1
        (1..s - 1).each do
          x = mod_exp(x, 2, n) # x = (x**2) % n
          return false if x == 1
          break if x == n - 1
        end
        return false if x != n - 1
      end

      true # probably
    end
def miller_rabin_prime?(n, g = 1000)
      return false if n == 1
      return true if n == 2

      d = n - 1
      s = 0

      while d.even?
        d /= 2
        s += 1
      end

      g.times do
        a = 2 + rand(n - 4)
        x = mod_exp(a, d, n) # x = (a**d) % n
        next if x == 1 || x == n - 1
        (1..s - 1).each do
          x = mod_exp(x, 2, n) # x = (x**2) % n
          return false if x == 1
          break if x == n - 1
        end
        return false if x != n - 1
      end

      true # probably
    end
An implementation of the miller-rabin primality test.
 See : http://primes.utm.edu/prove/merged.html
 See : http://rosettacode.org/wiki/Miller-Rabin_primality_test#Ruby
 See : https://crypto.stackexchange.com/questions/71/how-can-i-generate-large-prime-numbers-for-rsa
 See : https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

 Example : p primes = (3..1000).step(2).find_all {|i| miller_rabin_prime?(i,10)}