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

暗号理論の問題

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

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

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

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

誕生日問題の近似式 $1 - e^{- k (k - 1) / (2 N)}$ を使い、「衝突確率の近似値 $\geq \frac{1}{2}$ 」を $k$ についての不等式に書き直しましょう。

ヒント 2

$1 - e^{- x} \geq \frac{1}{2} ⟺ e^{- x} \leq \frac{1}{2} ⟺ x \geq lo g 2$ です。ここで $x = \frac{k ( k - 1 )}{2 N}$ とおきます。

ヒント 3

$N = 200$ を代入すると $k (k - 1) \geq 400 lo g 2 = 277.2$ となります。あとは $k = 16, 17, 18, \dots$ と $k (k - 1)$ を計算して、初めて $277.2$ 以上になる $k$ を探しましょう。

答えと解説

答えを見る

18

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

解説を読む

方針：誕生日問題の近似式 $p_{k} \approx 1 - e^{- k (k - 1) / (2 N)}$ を使い、「近似値 $\geq \frac{1}{2}$ 」を $k$ の不等式に直して解く。

ステップ 1（近似式の由来の確認）： $k$ 個のハッシュ値がすべて異なる確率は
$i = 0 \prod k - 1 (1 - \frac{i}{N})$
であり、 $1 - \frac{i}{N} \approx e^{- i / N}$ を使うと
$i = 0 \prod k - 1 e^{- i / N} = e^{- \frac{1}{N} \sum_{i = 0}^{k - 1} i} = e^{- \frac{k ( k - 1 )}{2 N}}$
となる。余事象をとって $p_{k} \approx 1 - e^{- k (k - 1) / (2 N)}$ である。

ステップ 2（不等式を立てる）： $N = 200$ より $2 N = 400$ なので、条件は
$1 - e^{- \frac{k ( k - 1 )}{400}} \geq \frac{1}{2} ⟺ e^{- \frac{k ( k - 1 )}{400}} \leq \frac{1}{2} .$
両辺の自然対数をとる（ $lo g$ は増加関数なので不等号の向きは変わらない）と
$- \frac{k ( k - 1 )}{400} \leq - lo g 2 ⟺ k (k - 1) \geq 400 lo g 2 = 400 \times 0.693 = 277.2.$

ステップ 3（最小の $k$ を探す）： $k (k - 1)$ は正の整数 $k$ について増加する。
- $k = 17$ のとき $k (k - 1) = 17 \times 16 = 272 < 277.2$
- $k = 18$ のとき $k (k - 1) = 18 \times 17 = 306 \geq 277.2$

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

補足： $k (k - 1) \approx k^{2}$ とみると $k \approx 2 N lo g 2 \approx 1.18 N$ で、 $200 \approx 14.1$ より $k \approx 16.7$ となり、出力数 $200$ に比べてずっと少ない約 $N$ の定数倍で衝突確率が $\frac{1}{2}$ を超えることがわかる。

答え： $18$

別解

近似値が $\frac{1}{2}$ 以上となる条件は $1 - e^{- k (k - 1) /400} \geq \frac{1}{2}$ である。
これは $e^{- k (k - 1) /400} \leq \frac{1}{2}$ と同値である。
両辺の自然対数をとると $\frac{k ( k - 1 )}{400} \geq lo g 2 = 0.693$ となる。
よって $k (k - 1) \geq 400 \times 0.693 = 277.2$ である。
$k (k - 1)$ は $k$ について増加するので、順に調べる。
$k = 17$ のとき $17 \cdot 16 = 272 < 277.2$ で不成立。
$k = 18$ のとき $18 \cdot 17 = 306 \geq 277.2$ で成立。
したがって最小の $k$ は $18$ である。

暗号理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題