#!/usr/koeki/bin/ruby
#coding: euc-jp

require 'prime'
def rsa_crypt(prime_p, prime_q)
 gcd, lcm = (prime_p - 1).gcdlcm(prime_q -1)
 n = prime_p * prime_q
 crypt = Array.new
 for k in 1 .. n - 1 
   power = Array.new  
   for l in 1 .. lcm + 1
     rem = k ** l % n
     power << rem
   end
   crypt << power
 end
 crypt
end

def rsa_decode(prime_p, prime_q, openkey)
  l = l0 = ( prime_p - 1 ) * ( prime_q - 1) 
  while true
    l += l0
    m = (l + 1) % openkey
    if m == 0
      break
    end
  end
  return ( l + 1 ) / openkey
end

r = 3
q = 7
s = 5

encrypt = "19 18 11 9"

c = rsa_crypt(r, q)

ph = encrypt.split(" ")

printf("復号鍵: %d\n", rsa_decode(r, q, s))

#復号する
# p dec 復号する秘密鍵はきめうちのとき d = 5 

dec = Array.new
for i in 0 .. c.length - 1
  dec << c[i][s-1]
end

for st in ph
  printf("%d ", dec[st.to_i - 1])
end

printf("\n復号終了\n")