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

暗号理論の問題

難易度 1教科書の例題レベル大学数学暗号理論

出力が $N = 1000$ 通りの値 ${0, 1, 2, \dots, 999}$ のどれかになるハッシュ関数 $H$ を考える。 $H$ はランダムオラクルとみなす。つまり、互いに異なる入力に対する出力は、それぞれ独立に $1000$ 通りの値から等確率で選ばれるものとする。

互いに異なる $k$ 個の入力（ $k$ は正の整数）のハッシュ値を計算したとき、少なくとも $1$ 組の衝突（同じハッシュ値をもつ $2$ つの入力）が起こる確率を $p_{k}$ とする。 $p_{k}$ を近似式
$p_{k} \approx 1 - e^{- \frac{k ( k - 1 )}{2 N}}$
で見積もる。この近似値が $\frac{1}{2}$ 以上となる最小の正の整数 $k$ を求めよ。ただし、 $lo g 2 = 0.6931$ として計算してよい（ $lo g$ は自然対数）。

この問題で使うもの

ハッシュの衝突確率（誕生日問題）（説明と入口の問題）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

誕生日問題の技能を使います。「すべて異なる確率」の余事象として衝突確率を考え、与えられた近似式 $1 - e^{- k (k - 1) / (2 N)}$ が $\frac{1}{2}$ 以上になる条件を不等式で表しましょう。

ヒント 2

$1 - e^{- \frac{k ( k - 1 )}{2 N}} \geq \frac{1}{2}$ は $e^{- \frac{k ( k - 1 )}{2 N}} \leq \frac{1}{2}$ と同じです。両辺の自然対数をとると $k (k - 1) \geq 2 N lo g 2$ が得られます。

ヒント 3

$N = 1000$ を代入すると $k (k - 1) \geq 1386.2$ です。 $1386.2 \approx 37.2$ なので、 $k = 37$ と $k = 38$ のあたりで $k (k - 1)$ を計算して比べてみましょう。

答えと解説

答えを見る

38

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

解説を読む

手順 1: 衝突確率の式を立てる。
$k$ 個のハッシュ値がすべて異なる確率は、 $1$ 個目は何でもよく、 $2$ 個目は $1$ 個目と異なる（確率 $1 - \frac{1}{N}$ ）、 $3$ 個目はそれまでの $2$ 個と異なる（確率 $1 - \frac{2}{N}$ ）、…と考えて
$i = 0 \prod k - 1 (1 - \frac{i}{N})$
である。余事象を考えると、衝突が起こる確率は
$p_{k} = 1 - i = 0 \prod k - 1 (1 - \frac{i}{N})$
となる。

手順 2: 近似式を確認する。
$x$ が小さいとき $1 - x \approx e^{- x}$ なので
$i = 0 \prod k - 1 (1 - \frac{i}{N}) \approx i = 0 \prod k - 1 e^{- \frac{i}{N}} = e^{- \frac{1}{N} \sum_{i = 0}^{k - 1} i} = e^{- \frac{k ( k - 1 )}{2 N}}$
となる。したがって $p_{k} \approx 1 - e^{- \frac{k ( k - 1 )}{2 N}}$ である。

手順 3: 不等式を解く。
$1 - e^{- \frac{k ( k - 1 )}{2 N}} \geq \frac{1}{2} ⟺ e^{- \frac{k ( k - 1 )}{2 N}} \leq \frac{1}{2}$
両辺の自然対数をとる（ $lo g$ は増加関数なので不等号の向きは変わらない）と
$- \frac{k ( k - 1 )}{2 N} \leq - lo g 2 ⟺ k (k - 1) \geq 2 N lo g 2$
$N = 1000$ を代入すると
$k (k - 1) \geq 2000 \times 0.6931 = 1386.2$

手順 4: 最小の $k$ を求める。
$k (k - 1)$ は正の整数 $k$ について増加する。
- $k = 37$ : $37 \times 36 = 1332 < 1386.2$
- $k = 38$ : $38 \times 37 = 1406 \geq 1386.2$

よって求める最小の $k$ は $38$ である。

（参考: $k (k - 1) \approx k^{2}$ とみると $k \approx 2 lo g 2 N \approx 1.18 \times 31.6 \approx 37.2$ となり、衝突確率が $\frac{1}{2}$ を超える $k$ はおよそ $N$ の定数倍であることがわかる。）

答え: $38$

別解

近似値が $\frac{1}{2}$ 以上となる条件は $1 - e^{- k (k - 1) / (2 N)} \geq \frac{1}{2}$ である。これは $e^{- k (k - 1) / (2 N)} \leq \frac{1}{2}$ と同値で、両辺の対数をとると $\frac{k ( k - 1 )}{2 N} \geq lo g 2$ となる。

$N = 1000$ 、 $lo g 2 = 0.6931$ を代入すると、 $k (k - 1) \geq 2000 \times 0.6931 = 1386.2$ である。

$k (k - 1)$ は $k \geq 1$ で単調増加なので、境界付近の値を調べる。
- $k = 37$ のとき、 $37 \cdot 36 = 1332 < 1386.2$ で不適。
- $k = 38$ のとき、 $38 \cdot 37 = 1406 \geq 1386.2$ で適する。

よって最小の $k$ は $38$ である。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題