本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成30年度 秋期 高度情報技術者試験問題と解説

問9

自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571、1168、1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ、全てのハッシュ値が衝突した。この時使用した除数は幾つか。

ア 193

イ 197

ウ 199

エ 211


正解


解説

除数をx、剰余をy とおくと、以下が成り立つ。
x×A+y = 571  ・・・@
x×B+y = 1168 ・・・A
x×C+y = 1566 ・・・B

A−@より (B−A)x=1168−571 = 597 ・・・C
B−@より (C−A)x=1566−571 = 995 ・・・D
B−Aより (C−B)x=1566−1168 = 398 ・・・E

C−Eより (B−A−C+B)x = 199

199は素数だから x =199
すなわち、除数は199である。

問8 目次 問10