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在下一页最上面喔～

谢谢...