平成30年度秋期 情報処理安全確保支援士 午前Ⅰ 問9

午前I 問09：同じ余りになる条件を差で考えよう

571、1168、1566 が同じ箱に入る、つまり同じ余りになるには、`571 ≡ 1168 ≡ 1566 (mod m)` になればいいよ。これは「それぞれの差が m で割り切れる」という意味だから、1168−571=597 と 1566−1168=398 の両方を割り切れる数を候補から探そう。

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

合同式をそのまま難しく見るのではなく、「同じ余りなら、引き算した差は m の倍数になるよね」と考えられるかがポイントだよ。

Hash Collision by Modulus

if hashes collide modulo m、 then all pairwise differences are divisible by m

1168-571 = 597\n1566-1168 = 398\ncommon divisor = 199

確認ポイント

• 元の値をそのまま割らない。
• 差を取って候補で割る。
• 199 を選ぶ。

正解

ウ

出典

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

選択肢ア

193で割ると、571の余りは185、1168の余りは10、1566の余りは22になるよ。余りがそろっていないので、同じロッカーに入る状態ではないんだ。だから不正解だよ。

選択肢イ

197で割ると、571の余りは177、1168の余りは183、1566の余りは187になるよ。3つとも同じ余りにならないので、同じ箱に入るハッシュ衝突は起きていないんだ。だから不正解だよ。

選択肢ウ（正解）

199で割ると、571も1168も1566も余りが173になるよ。つまり3つのキーが全部「173番の箱」に入るイメージで、ハッシュ値が衝突しているんだ。だからこれが正解だよ。

選択肢エ

211で割ると、571の余りは149、1168の余りは113、1566の余りは89で、全部バラバラになるよ。ハッシュ値の衝突は「同じ番号の窓口に3人が並ぶ」状態だけど、これは別々の窓口に行っているので不正解だよ。