Perfektes Hashing, finden einer injektive Hashfunktion

Question

Ich finde einfach kein Ansatz zum Lösen dieser Aufgabe..:

Im Folgenden sei U = N (natürliche Zahlen) und S = (0,3,7,18). Finden Sie eine Injektive Hashfunktion der Form:  h: S → (0, ... , m -1),  x ↦ ((ax+b) mod p) mod m

mit a, b, p, m ∈ Ν (natürliche Zahlen) und p prim. Die Zahlen m und p sollen hierbei so klein wie möglich sein.

Über Lösungsansätze oder weiteres wäre ich sehr dankbar! 

Answer 1

'Intelligentes Probieren': Der kleinste denkbare Wert für \(m\) ist \(m=4\), damit überhaupt genug  Hashwerte zur Verfügung stehen. Für \(p\) gilt die Bedingung, dass für jedes Paar \(\{s_i,s_j\} \space i \ne j \) aus \(S\) gelten muss

$$ s_i \not\equiv s_j \mod p$$

das ist recht schnell durchprobiert. So ist z.B. $$\begin{aligned} 0 &\equiv 18 &&\mod 2 \\ 0 &\equiv 3 &&\mod 3  \\ 3 &\equiv 18 &&\mod 5 \\  7 &\equiv 18 &&\mod 11 \end{aligned}$$ erst mit \(q=13\) sind alle Reste unterschiedlich.

Für die Parameter \(a\) und \(b\) fällt mir auch nur 'ausprobieren' ein, wobei \(a \lt p\) und \(b \lt p\) bleibt - alles andere macht keinen Sinn. Mit Hilfe eines Tabellenkalkulationsprogramms ist man dann sehr schnell bei \(a=5\) und \(b=1\). Somit ist

$$h(x) = ((5x + 1) \bmod 13) \bmod 4$$