RSA暗号2

RSA 暗号は、世界で広く使われている公開鍵暗号アルゴリズムです。

高橋くんは自分でも RSA 暗号を使ってみようと思いました。

そのためには鍵を作ることが必要です。

RSA 暗号の鍵生成は以下のような手順で行います。

RSA 暗号では、鍵を生成するために適当な素数 と、自然数 を選びます。

自然数 を、

と置きます。

ここで、 とすると、 は 未満の自然数で、 と互いに素である必要があります。（ はオイラーのφ関数 ）

自然数 を、

と置きます。

は多くの場合合成数であるため、 の計算は（拡張）ユークリッドの互除法により行います。

このようにして計算された値を使い、公開鍵と秘密鍵を作成することができます。

• 公開鍵:
• 秘密鍵:

相異なる素数 と正整数 が与えられます。

秘密鍵 を生成し、 と を出力してください。

ただし、 とし、 を となるような最小の非負整数とします。

• は素数であり、 である
• と は互いに素である
• 入力はすべて整数である

• 行目に を出力せよ。
• 行目に を出力せよ。

5 11 3

55
27

のとき、 となります。

97 997 64295

96709
10007

998244353 998244853 5

996492287418565109
199298457084415181

出力は ビット整数で表される範囲を超える可能性があります。