Universelles Hashing

Wissenschaft Informatik
#1

Hallo liebe Experten,

ich habe ein Verständnisproblem zu den c-universellen Klassen von Hashfunktionen.

Ich verstehe zunächst, dass wir eine Klasse von Hashfunktionen definieren, für die gilt, dass zwei verschiedene zu speichernde Werte mit höchstens folgender Wahrscheinlichkeit zur Kollision führt:

c * |H| / m

(c ist konstanter Wert aus R, |H| die Anzahl der Hashfunktionen und m die Anzahl der Hashwerte)

Als Beispiel für eine solche c-universelle Klasse wird nun folgende Menge beschrieben:

H = {h(a,b) | h(a,b)(x)=[(ax+b)mod N]mod m wobei a,b aus [0…N-1]} und N der Menge der abzubildenden Werte entspricht und gleichzeitig Primzahl sein muss.

Die Behauptung ist, dass dies eine c-universelle Klasse von Hashfunktionen darstellt, wobei sich der c-Wert aus (aufrunden(N/m)/(N/m))^2 darstellt
(„aufrunden“ bedeutet die Gauß-Klammer nach oben hier)

In dem Beweis stehe ich auf dem Schlauch.
Wir stellen zunächst fest, dass die Anzahl der Funktionen in H genau N^2 entspricht (logisch, alle möglichen Kombinationen für a und b).
Danach schnappen wir uns zwei beliebige, voneinander verschiedene Argumente x und y und wollen beweisen, dass die Anzahl der möglichen (a,b)-Kombinationen, die beide Argumente auf den gleichen Hashwert abbilden maximal (C*N^2)/m entspricht.

Jetzt kommen die 2 Knackpunkte:
Es wird argumentiert, dass im Falle der Gleichheit Werte q, r und s existieren (q aus [0…m-1] und r,s aus [0…(aufrunden(N/m))-1]), so dass folgende Gleichungen gelten:

ax + b = q + rm mod N
ay + b = q + sm mod N

Das sieht einfach aus, aber ich sehe die Richtigkeit der Gleichungen nicht. Ich konstruiere mir folgenden Fall (a=2, b=3, N=97, m=5, x=63). Daraus erhalte ich:

ax+b=129
**q+rm mod N

Wo ist mein Denkfehler?

Mache ich einfach weiter, so wird argumentiert, dass wegen der Primzahleigenschaft von N, ZN ein Körper ist. Deswegen soll jede Wahl für q, r und s genau nur eine Lösung in (a,b) haben. Kann mir das jemand kurz erklären, warum das so ist mit der Körpereigenschaft.

Der Rest ist Rechnerei und verstehe ich dann wieder, weil die Anzahl der (a,b)-Kombiationen dann genau m*(aufrunden(N/M))^2 entspricht. Dies führt nach Äquivalenzumformungen zu der Aussage m>=m.

Für eine kleine Hilfestellung wäre ich sehr dankbar.**

#2

ax + b = q + rm mod N
ay + b = q + sm mod N

Das sieht einfach aus, aber ich sehe die Richtigkeit der
Gleichungen nicht. Ich konstruiere mir folgenden Fall (a=2,
b=3, N=97, m=5, x=63). Daraus erhalte ich:

ax+b=129
**q+rm mod N

Wo ist mein Denkfehler?**

Ich denke mal, da muesste eigentlich ein „kongruent“ stehen, statt eines
Gleichheitszeichens. -> Werde Herrn Blum bei Gelegenheit drauf ansprechen :smile:

Ansonsten: Es muss ja
ax+b mod N mod m = ay+b mod N mod m gelten, damit es eine Kollision ist.

Mache ich einfach weiter, so wird argumentiert, dass wegen der
Primzahleigenschaft von N, ZN ein Körper ist.
Deswegen soll jede Wahl für q, r und s genau nur eine Lösung
in (a,b) haben. Kann mir das jemand kurz erklären, warum das
so ist mit der Körpereigenschaft.

  1. Dass Z_N ein Körper ist kannst Du leich nachrechnen. Der einige „Knackpunkt“
    ist die Nulteilerfreiheit, da N aber eine
    Primzahl ist, kann es kein a*b=N mit a \neq N und b \neq N geben.

  2. Am einfachsten versteht man es vielleicht über einen „Algorithmischen“ Beweis: Da das Teil ein Körper ist (= du kannst Dividieren), darfst Du das entstehende Gelichungssystem in den Variablen a und b mit dem Gaussschen Algorithmus lösen. Dieser liefert
    für zwei linear unabhängige Gleichungen (x \neq y) in zwei Variablen eine eindeutige Lösung. (Es geht natürlich auch „sauber“ über die Dimension des Raums und den Rang der Matrix, was im Prinzip das gleiche ist.)

ML