昨日のエントリの
(r個のシンボルに基づくXORベースの64 bitハッシュの衝突確率) = 1 - ( 1 - 1/(2^64) )^( Σ[n=1..floor[r/2]]{ C(r, n) } )
と、
これはXORするシンボルの数を増やしていることになるので、ハッシュの衝突確率はその分増大(劣化)する
というのは撤回死体、orz
まず式の方は、正解から言うと64 bit整数のHS(s(k)) r-1個のXORをランダムな情報源とみなすという単純な仮定の下では、
(r個のシンボルに基づくXORベースの64 bitハッシュの衝突確率) = 1/(2^64)
という単純な結論にしかならない。
昨日の間違った式は、r項のXORを2項に分割するそれぞれの仕方
(Σ[n=1..floor[r/2]]{ C(r, n) }通り)について、XOR結果がPに一致するか否かが独立であるとみなしてゐる。( ( 1 - 1/(2^64) )の冪乗であるあたりがそれ。)
しかし実際は、
A(1) (+) ( A(2) (+) A(3) (+) ... (+) A(r) )
がPと一致したらどう上記以外の2項のXORに分解しても結果はPに一致するし、Pと一致しなかったらどう2項のXORに分解しても結果はPに一致しない、という具合で、最初の2項への分割(任意)の結果に対して残りの分割の結果が完全に従属するから全く独立では無いから間違ってゐる、、、
「ハッシュの衝突確率はその分増大(劣化)する」のくだりについては、なんかXORするHS(s(k))が増えれば増えるほどPとの衝突確率が増えるとかどう考えてもおかしいやんか;;;
というわけで真実は64 bit整数のHS(s(k)) r-1個のXORをランダムな情報源とみなすという単純な仮定の下では
(r個のシンボルに基づくXORベースの64 bitハッシュの衝突確率) = 1/(2^64)
ぐらいのことしか言えない、