04:14:27)追加された行はこの色です。削除された行はこの色です。[#l3ddbfd1][定理]鳩の巣原理~n+1羽の鳩がn個の巣に入るとすれば、2羽以上の鳩が入る巣が少なくともひとつは存在する。[系]~ハッシュ値がκビットの場合、Hを2SUP{κ};+1回計算すると、必ず衝突ペアが求まる。[証明]κビットは、2SUP{κ};通りの組み合わせがある。よって、y=H(x)において、yは2SUP{κ};ある。~(xを鳩の数、yを巣の数と思えばよい)つまり、2SUP{κ};+1を考えると少なくともひとつは重複するものがある。鳩の巣原理より、366人集まると、誕生日が一致するペアが必ず(確率1で)存在する。誕生日は365通りからランダムに選ばれるので、直感的には誕生日が一致するペアが存在する確率はとても低いように感じる。実際には高い確率で誕生日が一致するペアが存在する。これを''バースディパラドックス''と呼ぶ。[定理]~q個のボールをn個のバケツにランダムに投げ入れたと仮定する。~このとき、2個以上のボールが入るバケツが少なくともひとつ存在する確率をPSUB{coll};とすると、次のようになる。0.3");[証明][証明]集合{aSUB{1};,...,aSUB{n};}からk個の(aSUB{1};,...,aSUB{n})を選んだとき、重複がひとつでもある確率をPSUB{coll};とし、その値を求めたい。q個のボールから2つ選ぶときのペアの総数はSUB{q};CSUB{2};である。a_1)");」が成り立つときである。このときの確率をqとすると、次のようになる。バケツがn個あり、それらからひとつ選択するので、1/nである。PSUB{coll};とqの関係は次のようになる。e^x");が成り立つ。このxに&mimetex("x=-\frac{i}{n}");を代入すると、次が成り立つ。これのi=1〜k-1までを両辺を掛け算すると、次のようになる。(*)より、次が成り立ち、展開していくと次のようになる。\frac{1}{2}");である。例:40人のクラスで同じ誕生日のペアが存在する確率を計算してみる。すると、次のようになる。よって、88%で誕生日が衝突するようなペアが存在するということである。して想像していた確率と数学的な確率が異なっているので、バースディパラドックスと呼ばれる所以である。[#g3b17d01][系]~ハッシュ値がκビットの場合、Hを2SUP{κ/2};回計算すると、0.3以上の確率で衝突ペアが求まる。[証明]y=H(x)において、xをボールの数、yをバケツの数と思えばよい。[問]任意のビット列から40ビットのハッシュ値を求めるハッシュ関数を考える。q個のビット列をランダムに選び、ハッシュ値を求め、衝突を見つけたい。衝突が見つかるような確率を1/2以上とするために、必要なビット列の個数qを求めよ。[解答]PSUB{coll};=1/2とすると、次のようになる。