平成30年度 秋期 応用情報技術者試験 午前 問27

二つの値の剰余が等しい（衝突する）ためには，二つの値の差が除数で割り切れる必要があります。
- 1168 − 571 ＝ 597
- 1566 − 1168 ＝ 398

597と398の両方を割り切る数を選択肢から探します（597 ＝ 3 × 199，398 ＝ 2 × 199）。

• ア: 193
  誤り。597 ÷ 193 ＝ 3 余り 18 となり，割り切れないので，571と1168の剰余は一致しません。

• イ: 197
  誤り。597 ÷ 197 ＝ 3 余り 6 となり，割り切れないので衝突しません。

• ウ: 199
  正しい。597 ＝ 199 × 3，398 ＝ 199 × 2 であり，どちらも割り切れます。実際に 571 mod 199 ＝ 173，1168 mod 199 ＝ 173，1566 mod 199 ＝ 173 となり，全てのハッシュ値が衝突します。

• エ: 211
  誤り。597 ÷ 211 ＝ 2 余り 175 となり，割り切れないので衝突しません。

答え

ウ: 199