平成21年度春期 情報処理安全確保支援士 午前Ⅰ 問3

割り算の「余り」でグループ分けしたとき、データが同じ部屋（衝突）になる条件は？

データを n で割った余り（ハッシュ値）で整理するとき、2つの違うデータ x と y が同じ余りになってぶつかってしまう（衝突する）のは、2つのデータの引き算の答え (x - y) がちょうど n の倍数になるときだよ。

この問題で問われていること

「余りが同じになる」という現象を、「2つの数字の差が割り切れる（nの倍数）」と言い換える数学のパズルとして整理しよう。

Hash Collision Condition

two keys collide under x mod n when they are congruent modulo n、 meaning their difference is a multiple of n

a mod n = b mod n\n(a - b) is multiple of n

確認ポイント

• 和ではなく差に注目する。
• 同じ余りになる条件を考える。
• 差が法の倍数かを確認する。

正解

イ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

これは不正解だよ。a+b が n の倍数でも、a mod n と b mod n が同じになるとは限らないんだ。ハッシュ値が同じになる条件は、足した結果ではなく、aとbの差がnの倍数かどうかだよ。たとえるなら、合鍵が合うか調べたいのに、2本の鍵の長さを足して見ているような感じで、必要な比較になっていないんだ。

選択肢イ（正解）

これは正解だよ。h(x)=x mod n は「nで割った余り」を見る仕組みだから、aとbが同じ箱に入るには、aを割った余りとbを割った余りが同じであればいいんだ。つまり、a-b が n でぴったり割り切れる状態だよ。たとえるなら、番号札aとbが違っても、窓口がn個しかないので、nずつ離れた番号は同じ窓口に呼ばれる感じだね。

選択肢ウ

これは不正解だよ。衝突するかどうかは「aとbの差」がnで割り切れるかで決まるんだ。「a+b」のように足し算した値を見ても、同じ余りになる条件とは限らないよ。たとえるなら、同じ窓口に並ぶかを知りたいのに、2人の番号札を足して判断しているようなもので、見るポイントがずれているんだ。

選択肢エ

これは不正解だよ。nが何かの倍数かどうかを見ても、aとbが同じ余りになるかは判断できないんだ。大事なのは、aとbをnで割ったときの余りが一致すること、つまり a-b が n の倍数になることだよ。たとえるなら、泥棒が同じ部屋に入ったかを知りたいのに、建物の階数だけを見ているようなもので、肝心の部屋番号の一致を確認できていないんだ。