#!/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 map_rsa_crypt(prime_p, prime_q)
  gcd, lcm = (prime_p - 1).gcdlcm(prime_q -1)
  n = prime_p * prime_q
  m = gcd * lcm + 1
  crypt = Array.new
  for k in 1 .. n - 1 
    power = Array.new  
    for l in 1 .. m
      rem = k ** l % n
      power << rem
    end
    crypt << power
  end
  crypt
end


def show_2dim_matrix(c)
  print(" " * 6)
  (0 .. c[0].length - 1).each{|j|
    printf("^%2d ", j + 1)
  }
  print("\n" + "-" * ( c[0].length * 4 + 5) + "\n")
  c.each{|line|
    printf("d=%2d|",c.rindex(line) + 1)
    line.each{|col|
      printf("%4d", col)
    }
    puts ""
  }
end

#STDERR.print("1 つめの素数 p = ")
#r = gets.to_i
r = 3
#STDERR.print("2 つめの素数 q = ")
#q = gets.to_i
q = 7

printf("1 つめの素数 p = %d,\t", r)
printf("2 つめの素数 q = %d,\t", q)

gcd, lcm = (r-1).gcdlcm(q-1)
printf("(p-1, q-1) の gcd = %d, lcd = %d\n", gcd, lcm)

printf("暗号生成: \n")

show_2dim_matrix(map_rsa_crypt(r, q))

STDERR.printf("公開鍵: 1 .. %d までの数で好きな数を選んでください (すなわち法は %d): ",
lcd - 1, lcd)

#s = gets.to_i
s = 5

printf("公開鍵: %d, 法は %d\n", s, lcd)