問題文


現在、世界中で使用されているRSA暗号の仕組みは以下の通り。 1.相異なる2つの素数を選び、とする。また、とする。 2.未満の正の整数で、と互いに素な数を1つ選ぶ。は公開鍵として公開される。 3.を満たすようなを求める。このは秘密鍵である。 4.平文暗号化する前の文以上未満の整数とし、これをとする。送り主は盗聴された場合に備え、そのものではなくで割った余りを送信する。 5.受け取り主は暗号文を受け取った上で、で割った余りがとなるようなを計算する。これにより暗号文を平文に復号することができる。

公開鍵及び文の長さを与えるので、以下の2つの問に答えられるプログラムを作成せよ。 1.平文列が与えられたときに、各を暗号化し暗号文列を出力せよ。 2.暗号文列が与えられたときに、各を復号し平文列を出力せよ。

制約


  • は相異なる素数であり、
  • である。また、と互いに素

入力


入力は以下のどちらかの形式で与えられる。 <暗号化>

encode
n e L
a_1 a_2 ... a_L

<復号>

decode
n e L
b_1 b_2 ... b_L

出力


計算結果を半角スペース区切りで出力せよ。

サンプル


入力1-A
encode
21 5 5
16 7 8 12 11
出力1-A
4 7 8 3 2

に対し、で割った余りを出力すれば良い。


入力1-B
decode
21 5 5
4 7 8 3 2
出力1-B
16 7 8 12 11

に対し、で割った余りがになるようなは1つに定まるので、それを出力すれば良い。


入力2-A
encode
2000000014 10001 5
314159265 358979323 846264338 327950288 419716939
出力2-A
1114575615 1064628669 1590103890 1142765810 529554705

を求める過程でのオーバーフローに注意せよ。


入力2-B
decode
2000000014 10001 5
1114575615 1064628669 1590103890 1142765810 529554705
出力2-B
314159265 358979323 846264338 327950288 419716939

数が大きすぎるので、と1つずつ調べて行っても間に合わない。さて、どうすれば良いか?

ヒント

の決め方から、においては整数と書けるのだが、2つ目の項の指数がの倍数かつの倍数であるということから何が言えるのだろうか?

Submit


Go (1.14)