Beweisen Sie die quadratische Antastfunktion

Question

Ich würde wirklich schätzen, wenn jemand helfen könnte, dieses Problem zu lösen. Die Frage ist: Betrachten Sie die folgende Hash-Funktion: h (k, i) = (h '(k) + (1/2) (i + i^2)) mod m, wobei m = 2^p für einige positive Ganzzahl p. Beweisen oder widerlegen, dass für jedes k, die Probe Sequenz ist eine Permutation von < 0, 1, 2, ..., m - 1>

Answer 1

Ja, ist es.

Nehmen wir an, h(k, i) = h(k, j).
Dann 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). Der zweite Term ist ungerade und 2m = 2^(p + 1), also
=>i = j (mod m).