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

正解：ウ

AI解説

正解はウ。ハッシュ値が衝突した(mod nが等しい)なら、キー値同士の差はnで割り切れる。1168−571＝597、1566−1168＝398、1566−571＝995であり、597＝3×199、398＝2×199、995＝5×199。共通の約数は199だけなので除数は199である。 ア: 193では571 mod 193＝571−2×193＝185、1168 mod 193＝10となり一致しない。差597などを割り切れない。 イ: 197では571 mod 197＝177、1168 mod 197＝? 197×5＝985、1168−985＝183で一致しない。差を割り切れない。 ウ: 正しい。571 mod 199＝173、1168 mod 199＝1168−995＝173、1566 mod 199＝1566−1393＝173で全て衝突する。 エ: 211では571 mod 211＝149、1168 mod 211＝? 211×5＝1055、余り113で一致しない。差を割り切れない。 💡 「mod nで等しい⇔差がnの倍数」が鍵。各値を割るより、値同士の差を取って共通因数を探す方が速い。剰余系の合同の性質は頻出テクニックである。