問7応用情報技術者 令和元年度 秋期

解説

正解は2。衝突は h(a)＝h(b)、つまり a mod n＝b mod n のときに起こる。aとbをnで割った余りが等しいことは、差a−bがnで割り切れること、すなわちa−bがnの倍数であることと同じ。例えばn＝10、a＝13、b＝23なら余りはどちらも3で、差の10は10の倍数になる。

• 1は、n＝10、a＝1、b＝9のように和が10の倍数でも、余りは1と9で衝突しない。
• 3は、n＝5、a＝3、b＝2なら5は和5の倍数だが、余りは3と2で衝突しない。
• 4は、n＝10、a＝13、b＝33なら衝突するのに、10は差20の倍数ではない。倍数の向きが逆。

根拠：剰余の性質（a mod n＝b mod n ⇔ a−bがnの倍数）。