高度情報処理技術者試験・情報処理安全確保支援士試験 令和4年度 秋期 午前I 問3

【正解】イ

ハッシュ表で衝突するのは、異なるキーをハッシュ関数に入力した結果が同じ値になるときです。したがって、キーaとbが衝突する条件は、a mod n＝b mod nです。aをnで割った商をp、余りをr、bをnで割った商をq、余りを同じくrとすると、a＝pn＋r、b＝qn＋rです。両式の差を取ると、a－b＝（p－q）nとなります。よってa－bはnの倍数であり、イが正解です。例えばn＝5、a＝12、b＝7なら、どちらの余りも2で、差の12－7＝5はnの倍数です。

アの条件は誤りです。a＋bがnの倍数でも、余りが同じとは限りません。例えばn＝5、a＝1、b＝4では和は5ですが、余りはそれぞれ1と4です。

ウの条件は誤りです。nがa＋bの倍数であることと、aとbをnで割った余りが一致することには直接の関係がありません。

エの条件は誤りです。これはnがa－bで割り切れるという条件であり、必要な「a－bがnで割り切れる」とは倍数関係が逆です。例えばn＝6、a＝8、b＝6では、6は差2の倍数ですが、余りは2と0で衝突しません。

【ポイント】 「同じ余りになる」という条件は、合同式ではa≡b（mod n）と表します。 これを変形したn｜（a－b）、すなわち「差がnの倍数」を覚えておくと、衝突条件を素早く判定できます。