修了試験 2021-06-13実施分 基本情報技術者試験 問8

解説

正解は2です。 ハッシュ関数で2つのキーが同じ値になる「衝突（シノニム）」の条件を問う問題です。 h(x)＝x mod n なので、衝突はaとbをnで割った余りが等しいときに起こります。 【計算】 a mod n ＝ b mod n ＝ r とおきます。 a ＝ n×p＋r、b ＝ n×q＋r と表せます（p、qは整数）。 a－b ＝ n×(p－q) となり、a－b はnの倍数です。 【選択肢別解説】 1：× a＋bがnの倍数でも衝突するとは限りません。 たとえばn＝5、a＝1、b＝4ではa＋b＝5ですが、余りは1と4で異なります。 2：○ 余りが等しいことは、差a－bがnで割り切れることと同じです。 したがってa－bがnの倍数のとき衝突します。 3：× nがa＋bの倍数でも、余りが等しいとは限りません。 たとえばa＝1、b＝2、n＝6では余りは1と2で異なります。 4：× nがa－bの倍数でも、余りが等しいとは限りません。 たとえばa＝7、b＝5、n＝4では余りは3と1で異なります。 【ポイント】 「aとbをnで割った余りが等しい」ことを、合同式でa≡b（mod n）と書きます。 これは「a－bがnの倍数」と同じ意味であり、ハッシュや暗号の問題でよく使われます。