令和6年度秋期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03：ハッシュの衝突は「同じ余り」になることだよ

ハッシュ値を `mod n` で求めるときは、割った余りが同じなら同じハッシュ値になるよ。つまり `a mod n = b mod n` というのは、たとえるなら2つの数が同じ番号の箱に入るようなもの。これは `a - b` が `n` で割り切れる、つまり `n` の倍数になることと同じ意味だよ。

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

ポイントは、合同式を「ハッシュ値がぶつかる条件」として読み替えられるかどうかだよ。余りが同じなら同じ場所に入る、だから衝突する、と考えよう。

ハッシュ衝突条件

`a mod n = b mod n` なら `a-b = kn` と表せる。

same remainder\n<=> a-b is multiple of n

確認ポイント

• 和ではなく差に着目する。
• `n` で割った余りが等しい条件を使う。
• 合同式の基本性質を使う。

正解

イ

出典

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

選択肢ア

a+bを見るのは方向が違うよ。余りが同じかを知りたいときは、二つの数がどれだけ離れているか、つまり差を見るんだ。合鍵が同じ鍵穴に合うかを調べるのに、2本の鍵の長さを足しても意味がないのと同じで、a+bがnの倍数かどうかでは判断できないよ。

選択肢イ（正解）

これは本来、「aとbをnで割った余りが同じ」ことを表す正しい条件だよ。たとえば7日ごとに同じ曜日が来るように、日数の差が7の倍数なら同じ曜日になるよね。同じように、a-bがnの倍数なら、aとbはnで割った余りが同じになるよ。

選択肢ウ

これも割り算の向きが違ううえに、見るべきものも差ではなく和になっているよ。余りが同じかは「aとbの差がn個刻みになっているか」で決まるんだ。nがa+bの倍数かを見ても、同じ窓口に戻ってくるかどうかは分からないので不正解だよ。

選択肢エ

これは「nの方が、a-bで割り切れる」という意味になっていて、向きが逆だよ。例えば同じ窓口番号に並ぶ人を見分けたいなら、大事なのは「人数差 a-b が窓口数 n でぴったり割れるか」なんだ。窓口数 n を人数差で割れるかは関係ないので不正解だよ。