暗号理論の問題
英字 文字を と数に対応させ、各文字 を
で暗号化する。この暗号の復号関数を
の形で表すとき、整数 ()の組 を求めよ。
この問題で使うもの
- アフィン暗号(説明と入口の問題)
この問題を解けるようになるまで(24 技能)
読み込み中…
右端(太枠)がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
アフィン暗号の復号関数 を使います。まず法 での の逆元を拡張ユークリッドの互除法で求めましょう。
ヒント 2
を逆にたどり、 となる整数 を見つけます。
ヒント 3
より 。あとは を展開し、定数項を 以上 以下に直します。
答えと解説
答えを見る
どこでつまずきましたか?(選ぶと、戻る場所を案内します)
解説を読む
復号関数は を について解いたものである。
手順 1: を求める。
なので逆元が存在する。互除法を行うと
これを逆にたどると
よって であり、 より 。
(確認:。)
手順 2: について解く。
より 。両辺に を掛けると
なので 。したがって
確認: (F)のとき 。 となり元に戻る。
よって 。
別解
より 。 の mod 26 での逆元を求める。 なので 。よって 。 なので 。ゆえに 、。
検算: のとき 、 より 。 のとき 、 より 。よって正しい。