暗号理論の問題

難易度 4大学院入試の標準レベル大学数学暗号理論

英字 $26$ 文字を $A = 0, B = 1, \dots, Z = 25$ と数に対応させ、鍵 $(a, b)$ のアフィン暗号
$E_{a, b} (x) \equiv a x + b (mod 26) (x \in {0, 1, \dots, 25})$
で 1 文字ずつ暗号化する。鍵は、 $1 \leq a \leq 25$ かつ $g cd (a, 26) = 1$ を満たす整数 $a$ と、 $0 \leq b \leq 25$ を満たす整数 $b$ の組 $(a, b)$ とする（全部で $12 \times 26 = 312$ 通り）。

ある鍵 $(a, b)$ について、同じ鍵で 3 回続けて暗号化すると、どの文字ももとの文字に戻る、すなわち
$E_{a, b} (E_{a, b} (E_{a, b} (x))) \equiv x (mod 26) (すべての x \in {0, 1, \dots, 25})$
が成り立つとする。このような鍵 $(a, b)$ の個数を求めよ（恒等写像になる鍵 $(1, 0)$ も数える）。

この問題で使うもの

アフィン暗号（説明と入口の問題）
合同式（説明と入口の問題）
剰余類環の単元群とオイラー関数（説明と入口の問題）

この問題を解けるようになるまで（27 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$E^{3} = E \circ E \circ E$ を $x$ の 1 次式 $a^{3} x + (定数)$ として計算し、恒等写像になる条件を $a$ と $b$ の合同式で書こう。

ヒント 2

条件は $a^{3} \equiv 1 (mod 26)$ かつ $b (a^{2} + a + 1) \equiv 0 (mod 26)$ 。中国剰余定理で $mod 2$ と $mod 13$ に分けて考えるとよい。

ヒント 3

$a^{3} \equiv 1 (mod 13)$ の解は $a \equiv 1, 3, 9$ なので、候補は $a = 1, 3, 9$ 。あとはそれぞれについて $a^{2} + a + 1$ を計算し、 $b (a^{2} + a + 1) \equiv 0 (mod 26)$ を満たす $b$ を数えよう。

答えと解説

答えを見る

27

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

3 回合成した写像. $E (x) = a x + b$ とすると
$E (E (x)) = a (a x + b) + b = a^{2} x + ab + b,$
$E^{3} (x) = a (a^{2} x + ab + b) + b = a^{3} x + b (a^{2} + a + 1) .$
これがすべての $x$ で $x$ に等しい条件は、 $x = 0$ を代入して $b (a^{2} + a + 1) \equiv 0$ 、 $x = 1$ を代入して $a^{3} \equiv 1$ が得られ、逆にこの 2 つが成り立てばすべての $x$ で成り立つ。よって条件は
$a^{3} \equiv 1 (mod 26), b (a^{2} + a + 1) \equiv 0 (mod 26) .$

$a$ の条件. $26 = 2 \cdot 13$ なので、中国剰余定理により $a^{3} \equiv 1 (mod 2)$ かつ $a^{3} \equiv 1 (mod 13)$ と同値。
- $mod 2$ : $a$ は奇数（ $g cd (a, 26) = 1$ から自動的に成り立つ）。
- $mod 13$ : $(Z /13 Z)^{\times}$ は位数 $12$ の巡回群で、 $3 ∣ 12$ だから $a^{3} \equiv 1$ の解はちょうど $3$ 個ある。 $3^{3} = 27 \equiv 1$ , $9^{3} = 729 = 56 \cdot 13 + 1 \equiv 1$ より、解は $a \equiv 1, 3, 9 (mod 13)$ 。

$1 \leq a \leq 25$ で奇数かつ $a \equiv 1, 3, 9 (mod 13)$ となるのは（ $1, 14$ / $3, 16$ / $9, 22$ のうち奇数のもの）
$a = 1, 3, 9$
で、いずれも $g cd (a, 26) = 1$ を満たす。

各 $a$ について $b$ の個数.
- $a = 1$ : $a^{2} + a + 1 = 3$ 。 $3 b \equiv 0 (mod 26)$ で、 $g cd (3, 26) = 1$ より $b \equiv 0$ 。 $1$ 個。
- $a = 3$ : $a^{2} + a + 1 = 13$ 。 $13 b \equiv 0 (mod 26)$ $⟺$ $b$ は偶数。 $0 \leq b \leq 25$ の偶数は $13$ 個。
- $a = 9$ : $a^{2} + a + 1 = 91 = 3 \cdot 26 + 13$ より $91 b \equiv 13 b (mod 26)$ 。 $13 b \equiv 0 (mod 26)$ $⟺$ $b$ は偶数で、 $13$ 個。

合計. $1 + 13 + 13 = 27$ 個。

（確認: 例えば鍵 $(3, 2)$ では $E (0) = 2$ , $E (2) = 8$ , $E (8) = 26 \equiv 0$ と 3 回で $0$ に戻る。一方 $(3, 1)$ では $E^{3} (0) = 13 \cdot 1 \equiv 13 \neq = 0$ となり条件を満たさない。）

別解

$E (x) = a x + b$ を 3 回合成すると $E^{3} (x) \equiv a^{3} x + b (a^{2} + a + 1) (mod 26)$ 。これが任意の $x$ で $x$ に等しい条件は、 $x = 0$ と $x = 1$ を代入して比較することにより、 $a^{3} \equiv 1$ かつ $b (a^{2} + a + 1) \equiv 0 (mod 26)$ （逆も成り立つ）。\n\n(1) $a^{3} \equiv 1 (mod 26)$ は中国剰余定理で mod 2 と mod 13 に分ける。mod 2: $a$ は奇数（ $g cd (a, 26) = 1$ と同じ）。mod 13: $a^{3} \equiv 1$ の解は $a \equiv 1, 3, 9$ （ $3^{3} = 27 \equiv 1$ , $9^{3} = 729 = 13 \cdot 56 + 1$ 。位数 3 の元は 2 個、1 と合わせて 3 個。 $(Z /13)^{\times}$ は位数 12 の巡回群なので $x^{3} = 1$ の解は丁度 3 個）。 $1 \leq a \leq 25$ の奇数でこれを満たすのは $a = 1, 3, 9$ 。\n\n(2) 各 $a$ について $b$ の条件:\n- $a = 1$ : $a^{2} + a + 1 = 3$ 。 $3 b \equiv 0 (mod 26)$ より $b = 0$ のみ。1 通り。\n- $a = 3$ : $a^{2} + a + 1 = 13$ 。 $13 b \equiv 0 (mod 26)$ より $b$ は偶数。 $b \in {0, 2, \dots, 24}$ の 13 通り。\n- $a = 9$ : $a^{2} + a + 1 = 91 = 13 \cdot 7$ 。 $91 b \equiv 0 (mod 26)$ は $13 \cdot 7 b \equiv 0$ 、すなわち $7 b$ が偶数、 $b$ が偶数。13 通り。\n\n合計 $1 + 13 + 13 = 27$ 。\n\n検算: $a = 3, b = 2$ : $E (x) = 3 x + 2$ , $E^{2} = 9 x + 8$ , $E^{3} = 27 x + 26 + 2 \cdot ...$ を直接計算すると $E^{3} (x) = 3 (9 x + 8) + 2 = 27 x + 26 \equiv x$ ✓。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる