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

正解：イ

AI解説

ハッシュ値の衝突とは、異なるキーが同じハッシュ値をもつことである。h(a)=h(b)すなわちa mod n=b mod nとなる条件は、aとbをnで割った余りが等しいこと、つまり差a−bがnで割り切れる(a−bがnの倍数である)ことと同値である。したがってイが正解である。 ア: a+bがnの倍数でも余りが等しいとは限らない。例えばn=10でa=3,b=7なら和は10の倍数だが余りは3と7で異なる。 イ: 正しい。a mod n=b mod n ⇔ (a−b) mod n=0 ⇔ a−bがnの倍数、という合同式の基本性質である。 ウ: nがa+bの倍数という条件は余りの一致とは無関係である。 エ: nがa−bの倍数(nがa−bで割り切れる)は関係が逆であり、衝突条件ではない。 💡 「余りが等しい⇔差が割り切れる」は合同式(a≡b mod n)の定義そのもの。迷ったら小さな具体値(n=5、a=7、b=2など)を代入して確かめるとよい。