この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

暗号理論の問題

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

出力が $5$ 通りしかない簡易ハッシュ関数 $H$ を考える。 $H$ はランダムオラクルとみなし、互いに異なる入力に対する出力は、それぞれ独立に $5$ 通りの値から等確率で選ばれるものとする。

攻撃者は互いに異なる入力 $m_{1}, m_{2}, m_{3}, \dots$ を順に選んで $H (m_{1}), H (m_{2}), H (m_{3}), \dots$ を $1$ 回ずつ計算し、すでに計算した出力のどれかと同じ出力が初めて得られた時点で計算をやめる（衝突の発見）。このとき計算した $H$ の値の個数を $T$ とする（たとえば $H (m_{1}) = H (m_{2})$ ならば $T = 2$ ）。

確率変数 $T$ の期待値 $E [T]$ を求めよ。

この問題で使うもの

ハッシュの衝突確率（誕生日問題）（説明と入口の問題）
確率の定義と和事象・余事象（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

「 $T > k$ 」がどんな事象かを考え、 $P (T > k)$ を求めてから期待値を計算する方針をとる。

ヒント 2

$T > k$ は最初の $k$ 個の出力がすべて異なることと同じで、 $P (T > k) = \frac{5 \cdot 4 \dots ( 5 - k + 1 )}{5 ^{k}}$ 。また $0$ 以上の整数値をとる確率変数では $E [T] = \sum_{k \geq 0} P (T > k)$ が成り立つ。

ヒント 3

$P (T > 0) = P (T > 1) = 1$ , $P (T > 2) = \frac{4}{5}$ , $P (T > 3) = \frac{12}{25}$ , $P (T > 4) = \frac{24}{125}$ , $P (T > 5) = \frac{24}{625}$ , $P (T > 6) = 0$ となる。あとはこれらを足し合わせる。

答えと解説

答えを見る

\frac{2194}{625}

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

解説を読む

出力の個数を $N = 5$ とする。 $T$ は $2$ 以上 $N + 1 = 6$ 以下の整数値をとる（ $6$ 個計算すれば鳩の巣原理により必ず衝突する）。

$P (T > k)$ の計算

$T > k$ は「最初の $k$ 個の出力がすべて異なる」ことと同じである。出力は独立に等確率で選ばれるので、 $1 \leq k \leq N$ に対して
$P (T > k) = \frac{N}{N} \cdot \frac{N - 1}{N} \dots \frac{N - k + 1}{N} = \frac{N !}{( N - k )! N ^{k}}$
である。また $P (T > 0) = 1$ 、 $k \geq N + 1$ では $P (T > k) = 0$ である。 $N = 5$ のとき
$P (T > 0) = 1, P (T > 1) = 1, P (T > 2) = \frac{4}{5}, P (T > 3) = \frac{4 \cdot 3}{5 ^{2}} = \frac{12}{25},$
$P (T > 4) = \frac{4 \cdot 3 \cdot 2}{5 ^{3}} = \frac{24}{125}, P (T > 5) = \frac{4 \cdot 3 \cdot 2 \cdot 1}{5 ^{4}} = \frac{24}{625} .$

期待値の計算

$T$ は $0$ 以上の整数値をとる確率変数なので、 $T = \sum_{k = 0}^{\infty} 1 [T > k]$ と書けることから
$E [T] = k = 0 \sum \infty P (T > k)$
が成り立つ。よって
$E [T] = 1 + 1 + \frac{4}{5} + \frac{12}{25} + \frac{24}{125} + \frac{24}{625} = \frac{625 + 625 + 500 + 300 + 120 + 24}{625} = \frac{2194}{625} .$

（確認） $P (T = k) = P (T > k - 1) - P (T > k)$ から $P (T = 2) = \frac{1}{5}$ , $P (T = 3) = \frac{8}{25}$ , $P (T = 4) = \frac{36}{125}$ , $P (T = 5) = \frac{96}{625}$ , $P (T = 6) = \frac{24}{625}$ で、和は $\frac{125 + 200 + 180 + 96 + 24}{625} = 1$ 。これより $E [T] = \frac{2 \cdot 125 + 3 \cdot 200 + 4 \cdot 180 + 5 \cdot 96 + 6 \cdot 24}{625} = \frac{250 + 600 + 720 + 480 + 144}{625} = \frac{2194}{625}$ となり一致する。

したがって $E [T] = \frac{2194}{625}$ （ $\approx 3.51$ ）である。

別解

$T > k$ は、最初の $k$ 個の出力がすべて異なる事象である。 $P (T > k) = \frac{5 \cdot 4 \dots ( 5 - k + 1 )}{5 ^{k}}$ ( $0 \leq k \leq 5$ )、 $k \geq 6$ では鳩の巣原理より $P (T > k) = 0$ （ $T \leq 6$ ）。

$P (T > 0) = 1$ , $P (T > 1) = 1$ , $P (T > 2) = \frac{4}{5}$ , $P (T > 3) = \frac{4 \cdot 3}{25} = \frac{12}{25}$ , $P (T > 4) = \frac{4 \cdot 3 \cdot 2}{125} = \frac{24}{125}$ , $P (T > 5) = \frac{4 !}{5 ^{4}} \cdot \frac{1}{1} \cdot \frac{5 !}{5 ^{5}} \cdot \frac{1}{1}$ ではなく $\frac{5 !}{5 ^{5}} = \frac{24}{625}$ 。

$E [T] = \sum_{k \geq 0} P (T > k) = 1 + 1 + \frac{4}{5} + \frac{12}{25} + \frac{24}{125} + \frac{24}{625} = \frac{625 + 625 + 500 + 300 + 120 + 24}{625} = \frac{2194}{625}$ 。

検算: $P (T = 2) = \frac{1}{5}$ , $P (T = 3) = \frac{4}{5} \cdot \frac{2}{5} = \frac{8}{25}$ , $P (T = 4) = \frac{12}{25} \cdot \frac{3}{5} = \frac{36}{125}$ , $P (T = 5) = \frac{24}{125} \cdot \frac{4}{5} = \frac{96}{625}$ , $P (T = 6) = \frac{24}{625}$ 。合計 $\frac{125 + 200 + 180 + 96 + 24}{625} = 1$ 。 $E [T] = \frac{2 \cdot 125 + 3 \cdot 200 + 4 \cdot 180 + 5 \cdot 96 + 6 \cdot 24}{625} = \frac{250 + 600 + 720 + 480 + 144}{625} = \frac{2194}{625}$ 。一致する。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題