dh-key-study1.rb

#!/usr/bin/env ruby

# https://goo.gl/JJ8BaU
class Integer
  def prime?
    n = self.abs()
    return true if n == 2
    return false if n == 1 || n & 1 == 0
    d = n-1                                 # nは奇数だからdは偶数
    d >>= 1 while d & 1 == 0                # n-1 = d * 2^s
    20.times do                             # 20 は上の説明の k に相当
      a = rand(n-2) + 1                     # 1 <= a <= n-2
      t = d
      y = ModMath.pow(a,t,n)                # a^d mod n
      while t != n-1 && y != 1 && y != n-1
        y = (y * y) % n                     # a^(d * 2^r) mod n を求める
        t <<= 1                             # 最大s回繰り返す（s回右シフト後: t = d * 2^s = n-1）
      end
      # ループが終わった時点で、
      # 1. tが奇数 => t == d => 一回もループが起きてない => a^d mod n が 1 or n-1
      #      a^d mod n = 1 だったら、素数の可能性あり（定理）
      #      a^(d*2^0) mod n = n-1 だったら、素数の可能性あり（定理）
      #      つまり、tが奇数だったら、素数の可能性あり => 別のランダムな数で同じことを繰り返す
      # 2. それ以外の場合で、y != n-1 => a^(d * 2^r) mod n = n-1 (r > 0) => 素数ではない（定理）
      # y = 1 となった時点でループを脱するのは、それ以降のループを繰り返しても y = 1 となるだけで、やる意味がないから
      return false if y != n-1 && t & 1 == 0
    end
    return true
  end
end

module ModMath
  def ModMath.pow(base, power, mod)
    result = 1
    # 42 mod n = (2^1 mod n) * (2^3 mod n) * (2^5 mod n) と分解して求める
    while power > 0
      result = (result * base) % mod if power & 1 == 1
      base = (base * base) % mod
      power >>= 1;
    end
    result
  end
end

# http://goo.gl/eDV8Ec
def findGP(nTry, maxG)
  nTry.times {
    q = rand(maxG*10)
    next unless q.prime?
    p = 2*q + 1
    next unless p.prime?
    nTry.times {
      g = rand(maxG)
      next if g < 3
      next if ModMath.pow(g,2,p) == 1
      next if ModMath.pow(g,q,p) == 1
      return g, p
    }
    return nil, nil
  }
end

if __FILE__ == $0
  g, p = findGP 100, 100
  if g && p
    puts "found g:#{g} p:#{p}"
  else
    puts "not found"
  end
end