1. paizaラーニングトップ
  2. レベルアップ問題集
  3. ユークリッドの互除法メニュー(言語選択)
  4. 問題一覧
  5. RSA 暗号の解読(1文字)

ユークリッドの互除法メニューのサムネイル
RSA 暗号の解読(1文字)(paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

ここまで学んできた知識を利用して、RSA 暗号を解いてみましょう。
RSA 暗号を解読するために、その暗号化・解読方法をおさらいしましょう。

<準備>
適当な素数 p , q を用意し、 n = pq , n' = (p-1)(q-1) とおく。
e は gcd(e , n') = 1 を満たす適当な整数とし、あらかじめ de ≡ 1 (mod n') を満たす自然数 d を用意する。

<手順>
1. 受信者は n と e を公開しておく。
2. 送信者は、数値 M を送信したい時は、代わりに数値 E = M^e mod n を送信する。
3. E^d mod n を求めると元の数値 M が得られる。

今回送信者が送信した暗号化前の数字は 1 文字のアルファベット・記号の ASCII コード になっています。
復号に必要な整数 p,q,e,E が与えられるので、RSA 暗号を解読し、暗号化前の数値が表す文字を出力しましょう。

入力される値

p q e E


・1 行で、整数 p , q , e , E が与えられます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

・1 行で、暗号化前の数字を ASCII コードに基づいて変換した時に得られる 1 文字を出力してください。
・また、出力の末尾には改行を入れてください。

条件

・1 ≦ p , q ≦ 100,000
・p,q は素数である。
・p ≠ q
・1 ≦ e ≦ 10,000
・e は問題文中の条件を満たす。
・1 ≦ E < pq

入力例1

23917 23929 8731 109861231

出力例1

K

入力例2

21283 21313 2843 315549360

出力例2

p

問題一覧へ戻る

ページの先頭へ戻る