009: 「小さな鍵、大きな秘密」のヒント

問題 / 解答

難易度: ☆☆

ヒント1

p = 61 と q = 53 は、前問の primes_up_to(100) で素数として確認できます。 n は p * q です。

ヒント2

phi は n ではなく、(p - 1) * (q - 1) です。 e と phi が互いに素でないと、d は求まりません。 互いに素かどうかは、035の gcd で判定できます。

ヒント3

d は、e * d を phi で割った余りが1になる数です。 Pythonでは、pow(e, -1, phi) でこのような数を求められます。

ヒント4

暗号化と復号では、巨大なべき乗そのものを作る必要はありません。 pow(message, e, n) のように第3引数を使うと、剰余を取りながらべき乗を計算できます。