102交大 計算機系統 第6題
The ideal one way hash function is collision free. Given y=h(x).
Suppose x is of infinite length and y is of 8 bits.
What is the probability that two different inputs, x and x', of the hash function collide?
Ans.2/256=1/128
原因為何?
矛盾:y=h(x)為collision free, x and x'不同,怎麼可能產生collide?
機率應該為0?

這題答案應該是1/256唷，ideal說的是理想情況，實際上只能越低越好。x和x'不一樣，但是透過h(x)的轉換可能會對到同一個bucket，而y有8bits，所以有2^8個bucket，碰撞機率為1/256。

謝謝 1/256我就可以理解了但是選項沒有1/256...只有(a)0 (b)1 (c)1/8 (d)1/128

1/256在下一頁最上面喔～

謝謝...