증명 이차 탐침 기능

Question

누군가가이 문제를 해결하는 데 도움이된다면 정말 감사하겠습니다. 문제는 다음과 같습니다. h (k, i) = (h '(k) + (1/2) (i + i^2)) mod m, 여기서 m = 2^p 정수 p. 프로브 시퀀스는 임의의 k에 대해 < 0, 1, 2, ..., m-1>

Answer 1

의 순열입니다.

h(k, i) = h(k, j)이라고 가정합시다.
이어서 h'(k) + 1/2 * i * (i + 1) = h'(k) + 1/2 * j * (j + 1) (mod m) < =>
1/2 * i * (i + 1) = 1/2 * j * (j + 1) (mod m) =>
i * (i + 1) = j * (j + 1) (mod 2m) < =>i * i - j * j + i - j = 0 (mod 2m) < =>
(i - j) * (i + j + 1) = 0 (mod 2m). 두 번째 항은 홀수이고 2m = 2^(p + 1)이므로
i = j (mod 2m) =>i = j (mod m)입니다.