問題文

現在、世界中で使用されているRSA暗号の仕組みは以下の通り。$\\$ 1.相異なる2つの素数$p,q$を選び、$n=pq$とする。また、$\phi(n)=(p-1)(q-1)$とする。$\\$ 2.$\phi(n)$未満の正の整数で、$\phi(n)$と互いに素な数$e$を1つ選ぶ。$n,e$は公開鍵として公開される。$\\$ 3.$de\equiv1({\rm mod}\ \ \phi(n))$を満たすような$d$を求める。この$d$は秘密鍵である。$\\$ 4.平文$($暗号化する前の文$)$を$0$以上$n$未満の整数とし、これを$a$とする。送り主は盗聴された場合に備え、$a$そのものではなく$a^e$を$n$で割った余り$b$を送信する。$\\$ 5.受け取り主は暗号文$b$を受け取った上で、$a^e$を$n$で割った余りが$b$となるような$a$を計算する。これにより暗号文を平文に復号することができる。

公開鍵$n,e$及び文の長さ$L$を与えるので、以下の2つの問に答えられるプログラムを作成せよ。$\\$ 1.平文列$a_1,a_2,\cdots,a_L$が与えられたときに、各$a_i$を暗号化し暗号文列$b_1,b_2,\cdots,b_L$を出力せよ。$\\$ 2.暗号文列$b_1,b_2,\cdots,b_L$が与えられたときに、各$b_i$を復号し平文列$a_1,a_2,\cdots,a_L$を出力せよ。

制約

• $p,q$は相異なる素数であり、$pq\leq2\times10^9+1000$
• $n=pq$である。また、$e$は$\phi(n)=(p-1)(q-1)$と互いに素
• $0\leq a_i,b_i<n$
• $1\leq L\leq10^5$

入力

入力は以下のどちらかの形式で与えられる。$\\$ ＜暗号化＞

encode
n e L
a_1 a_2 ... a_L

$\\$ ＜復号＞

decode
n e L
b_1 b_2 ... b_L

出力

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

サンプル

encode
21 5 5
16 7 8 12 11

4 7 8 3 2

各$a_i$に対し、${a_i}^5$を$21$で割った余りを出力すれば良い。

decode
21 5 5
4 7 8 3 2

16 7 8 12 11

各$b_i$に対し、${a_i}^5$を$21$で割った余りが$b_i$になるような$a_i$は1つに定まるので、それを出力すれば良い。

encode
2000000014 10001 5
314159265 358979323 846264338 327950288 419716939

1114575615 1064628669 1590103890 1142765810 529554705

${a_i}^{10001}$を求める過程でのオーバーフローに注意せよ。

decode
2000000014 10001 5
1114575615 1064628669 1590103890 1142765810 529554705

314159265 358979323 846264338 327950288 419716939

数が大きすぎるので、$2^{10001},3^{10001},\cdots$と1つずつ調べて行っても間に合わない。さて、どうすれば良いか？$\\$ $\\$

ヒント$\\$

$d$の決め方から、${\rm mod}\ n$において$b^d\equiv a^{ed}=a^{l(p-1)(q-1)+1}=a\cdot a^{l(p-1)(q-1)}\ (l$は整数$)$と書けるのだが、2つ目の項の指数が$p-1$の倍数かつ$q-1$の倍数であるということから何が言えるのだろうか？