2018年度 秋期 エンベデッドシステムスペシャリスト 午前I 問9

この問題は、ハッシュ関数における衝突（異なるキー値が同じハッシュ値になること）の性質を利用したものです。使用された除数dは、入力値 571, 1168, 1566 をdで割った余りが全て同じになるような自然数です。これは、これらの値の差がdの倍数になることを意味します。具体的には、1168 - 571 = 597、1566 - 1168 = 398、1566 - 571 = 995 がdで割り切れる必要があります。つまり、dは597, 398, 995 の公約数でなければなりません。これらの数の最大公約数を求めると199になります。選択肢の中で199だけがこれらの差を割り切るため、これが使用された除数です。例えば、571 ÷ 199 = 2 余り 173、1168 ÷ 199 = 5 余り 173、1566 ÷ 199 = 7 余り 173となり、ハッシュ値は全て173で衝突します。他の選択肢はこれらの差を割り切らないため、全てのハッシュ値が衝突するという条件を満たしません。