暗号理論の問題

難易度 3期末試験の応用レベル証明問題大学数学暗号理論

$p$ を素数とし、 $Z_{p} = Z / p Z$ を $p$ を法とする剰余類全体とする。整数 $a, b$ は $a \neq \equiv 0 (mod p)$ かつ $a \neq \equiv 1 (mod p)$ をみたすとし、アフィン暗号の暗号化写像 $f : Z_{p} \to Z_{p}$ を
$f (x) = a x + b (mod p)$
で定める。正の整数 $r$ に対して、 $f$ を $r$ 回合成した写像を $f^{(r)} = r 個 f \circ f \circ \dots \circ f$ と書く。

正の整数 $r$ について、「すべての $x \in Z_{p}$ に対して $f^{(r)} (x) = x$ が成り立つ（すなわち、同じ鍵で $r$ 回暗号化すると必ず平文に戻る）」ための必要十分条件は $a^{r} \equiv 1 (mod p)$ であること（とくにこの条件は $b$ によらないこと）を証明せよ。

ただし、 $p$ が素数で $c \neq \equiv 0 (mod p)$ ならば、 $cy \equiv 0 (mod p)$ をみたす整数 $y$ は $y \equiv 0 (mod p)$ に限ることは用いてよい。

この問題で使うもの

合同式（説明と入口の問題）
等差・等比数列の和と Σ（説明と入口の問題）
アフィン暗号（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

まず $f^{(r)} (x)$ を $x$ の 1 次式の形で求めましょう。 $r$ についての帰納法が使えます。必要性と十分性は分けて示します。

ヒント 2

$f^{(r)} (x) = a^{r} x + (1 + a + \dots + a^{r - 1}) b$ となります。また $(a - 1) (1 + a + \dots + a^{r - 1}) = a^{r} - 1$ です。

ヒント 3

$a^{r} \equiv 1$ なら $(a - 1) S_{r} \equiv 0$ で、 $a \neq \equiv 1$ と $p$ が素数であることから $S_{r} \equiv 0$ がいえます。逆向きは $x = 0$ と $x = 1$ を代入してみましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

$f^{(r)} (x) \equiv a^{r} x + (1 + a + \dots + a^{r - 1}) b$ を帰納法で正しく導いている（3 点）
$(a - 1) (1 + a + \dots + a^{r - 1}) = a^{r} - 1$ を示している（1 点）
十分性で、 $a^{r} \equiv 1$ と $a \neq \equiv 1$ 、 $p$ が素数であることから定数項の係数が $0$ になることを導き、 $b$ によらず $f^{(r)}$ が恒等写像になることを示している（3 点）
必要性で $x = 0$ と $x = 1$ を代入し、差をとって $a^{r} \equiv 1$ を導いている（2 点）
必要十分条件であることを結論として述べている（1 点）

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

模範解答を読む

方針. $f^{(r)}$ を $x$ の 1 次式として求め、その定数項が $a^{r} \equiv 1$ のとき自動的に $0$ になることを示す。以下、合同式はすべて $p$ を法とする。

ステップ 1: $f^{(r)}$ の形. $S_{r} = 1 + a + a^{2} + \dots + a^{r - 1}$ とおき、すべての正の整数 $r$ とすべての $x \in Z_{p}$ について
$f^{(r)} (x) \equiv a^{r} x + S_{r} b (1)$
が成り立つことを $r$ についての数学的帰納法で示す。
- $r = 1$ のとき: $S_{1} = 1$ で、 $f^{(1)} (x) = f (x) = a x + b$ だから成り立つ。
- ある $r \geq 1$ で $(1)$ が成り立つと仮定する。 $Z_{p}$ では和と積について分配法則・結合法則が成り立つので
$f^{(r + 1)} (x) = f (f^{(r)} (x)) \equiv a (a^{r} x + S_{r} b) + b = a^{r + 1} x + (a S_{r} + 1) b .$
ここで $a S_{r} + 1 = a + a^{2} + \dots + a^{r} + 1 = S_{r + 1}$ なので、 $r + 1$ のときも $(1)$ が成り立つ。

よって $(1)$ はすべての正の整数 $r$ で成り立つ。

ステップ 2: $S_{r}$ と $a^{r}$ の関係. 展開して打ち消し合いを見ると
$(a - 1) S_{r} = (a + a^{2} + \dots + a^{r}) - (1 + a + \dots + a^{r - 1}) = a^{r} - 1. (2)$

ステップ 3: 十分性（ $\Leftarrow$ ）. $a^{r} \equiv 1$ と仮定する。 $(2)$ より $(a - 1) S_{r} \equiv 0$ である。仮定 $a \neq \equiv 1$ より $a - 1 \neq \equiv 0$ なので、用いてよい事実（ $c = a - 1$ , $y = S_{r}$ ）から $S_{r} \equiv 0$ である。したがって $(1)$ より、任意の $x \in Z_{p}$ で
$f^{(r)} (x) \equiv 1 \cdot x + 0 \cdot b = x .$
この議論で $b$ には何の条件も使っていない。

ステップ 4: 必要性（ $\Rightarrow$ ）. すべての $x \in Z_{p}$ で $f^{(r)} (x) = x$ と仮定する。 $0, 1 \in Z_{p}$ を代入すると、 $(1)$ より
$x = 0 : S_{r} b \equiv 0, x = 1 : a^{r} + S_{r} b \equiv 1.$
2 式目から 1 式目を引いて $a^{r} \equiv 1$ を得る。

補足. 仮定 $a \neq \equiv 0$ は $f$ が全単射（復号できる暗号）であるための条件で、上の同値の証明では使っていない。一方、仮定 $a \neq \equiv 1$ はステップ 3 で本質的に使っている（ $a \equiv 1$ , $b \neq \equiv 0$ のときは $f^{(r)} (x) \equiv x + r b$ となり、 $a^{r} \equiv 1$ でも $f^{(r)}$ が恒等写像とは限らない）。

結論. ステップ 3, 4 より、すべての $x \in Z_{p}$ で $f^{(r)} (x) = x$ となるための必要十分条件は $a^{r} \equiv 1 (mod p)$ であり、この条件は $b$ によらないことが示された。

この問題の確認

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

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

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