Schwierigkeiten beim Verstehen der wenigen Schritte im Beweis: "Die Klasse $ \ Mathscr {h} _ {p, m} $ of Hash-Funktionen ist universell"

Question

Ich ging durch den Text Einführung in Algorithmen von Cormmen et. al Wo ich den folgenden Auszug in Bezug auf den besagten Beweis kam, und die Schritte, in denen ich Schwierigkeiten hatte, sind mit $ \ Dagger $ und $ \ Dagger \ Dolch $ .

Entwerfen einer universellen Klasse von Hash-Funktionen

$ P $ ist eine Prime-Nummer groß genug, so dass jeder mögliche Taste $ K $ in ist Der Bereich $ 0 $ bis $ P - 1 $ , inklusive. Lassen Sie $ z_p $ den Set $ \ {0, 1, ..., P - 1 \} $ , und lassen Sie $ z_p ^ * $ den Set $ \ {1, 2, ..., p - 1 \} $ .Ahn der Annahme, dass die Größe des Tastenuniversums größer ist als die Anzahl der Slots $ M $ in der Hash-Tabelle, Wir haben $ p> M $ .

Wir definieren jetzt die Hash-Funktion $ H_ {A, B} $ für jeden $ a \ in z_p ^ * $ und jeder $ b \ in z_p $ :

$ h_ {a, b}= ((a.k + b) \ mod p) \ mod m $ .

Die Familie aller solchen Hash-Funktionen:

$$ \ Mathscr {H} _ {p, m}={h_ {a, b}: a \ in z_p ^ *, b \ in z_p \} $ $

---

theorem: Die Klasse $ \ mathscr {h} _ {p, m} $ von Hash-Funktionen ist universell.

---

Beweis:

Betrachten Sie zwei verschiedene Tasten $ K $ und $ L $ von $ z_p $ , so dass $ k \ neq l $ . Für eine bestimmte Hash-Funktion $ H_ {A, B} $ Wir lassen

$$ R= (AK + B) \ mod p $$ ,

$$ s= (AL + B) \ mod p $$ .

Wir beachten zum ersten Mal, dass $ r \ neq s $ . Warum? Beobachten Sie das, was

$$ R - s= A (k - l) (\ mod p) $$ $$ .

Es folgt, dass $ г \ neq s $ da $ P $ Prime und beide $ A $ und $ (k - l) $ sind ungleich Null Modulo $ p $ , und so muss ihr Produkt auch nicht null modulo $ p $

deshalb während der Berechnung von $ h_ {a, b} $ in $ \ mathscr {h} _ {p, m} $ , unterschiedliche Eingänge $ K $ und $ L $ map to Eindeutige Werte $ R $ und $ s $ modulo $ p $ ; Es gibt noch keine Kollisionen auf der MOD-P-Ebene. mehr darüber hinaus, jeder der möglichen $ p (p - 1) $ Auswahlmöglichkeiten für das Paar $ ( a, b) $ mit $ а \ neq 0 $ Erträgt ein anderes resultierendes Paar $ (R, S ) $ mit $ r \ neq s $ , da wir für $ a $ lösen können und $ B $ gegeben $ R $ und $ s $ $ ^ \ dagger $ :

$$ A= ((R - S) ((K - L) ^ {- 1} \ mod p)) \ mod p $$ , < / p>

$$ B= (R - AK) \ Mod p $$ ,

wobei $ ((k - l) ^ {- 1} \ mod p) $ den einzigartigen multiplikativen inversen, modulo p von $ k - L $ . Da gibt es nur $ P (P - 1) $ Mögliche Paare $ (R, S) $ mit $ г \ neq s $ , es gibt eine Eins-zu-Eins-Korrespondenz zwischen Paaren $ (A, B) $ < / span> mit $ a \ neq 0 $ und paare $ (r, s) $ mit $ r \ neq s $ . Somit für jedes gegebene Paar von Eingängen $ K $ und $ L $ , wenn wir $ (A, B) $ gleichmäßig von $ Z_P ^ * \ MACHE Z_P $ , dem resultierenden Paar $ (R, S) $ ist gleichermaßen wahrscheinlich ein paar unterschiedliche Werte Modulo p.

Es folgt dann, dass die Wahrscheinlichkeit, dass eindeutige Schlüssel $ K $ a

ND $ L $ Collide ist gleich der Wahrscheinlichkeit, dass $ R \ EQUIV S (\ mod m) $ Wenn $ R $ und $ S $ zufällig als unterschiedliche Werte ausgewählt wird MODULO $ P $ . für einen bestimmten Wert von $ r $ , der $ p - 1 $ Mögliche verbleibende Werte für $ s $ , die Anzahl der Werte $ s $ so, dass $ s \ neq r $ und $ S \ EQUIV R (\ mod m) $ ist höchstens $ ^ {\ Dagger \ Dolch} $

$$ \ lceil p / m \ RCEIL - 1 <(P + M - 1) / m) - 1 $$ $$= (P-1) / M $$ .

die Wahrscheinlichkeit, dass $ s $ mit $ R $ kollidiert, wenn Red Modulo $ M $ ist höchstens $ ((P-L) / m) / (P - 1)= 1 / M $ .

daher für jedes Paar von unterschiedlichen Werten $ k, l \ in z_p $ ,

$$ PR \ {h_ {a, b} (k)= h_ {a, b} (l) \} \ leq 1 / m $$

so dass $ \ mathscr {h} _ {p, m} $ in der Tat universell ist.

---

Zweifeln:

Ich konnte die folgenden Aussagen im Beweis nicht verstehen:

$ \ Dagger $ : jeder der möglichen $ p (p - 1) $ Wahlmöglichkeiten für das Paar $ (A, B) $ mit $ \ \ neq 0 $ Erträgt ein anderes resultierende Paare $ (R, S) $ mit $ r \ neq s $ , da wir löst werden können $ A $ und $ B $ angegeben $ R $ < / span> und $ s $

Warum, "wir können für $ A $ und $ B $ gegeben $ R $ und $ S $ " $ \ Impliziert $ "Jeder der möglichen $ P (P - 1) $ Auswahlmöglichkeiten für das Paar $ (A, B) $ mit $ а \ neq 0 $ ergibt ein anderes resultierendes Paar $ (R, S) $ mit $ г \ neq s $ "

---

$ \ Dagger \ Dagger $ : für einen bestimmten Wert von $ r $ , der $ P - 1 $ mögliche verbleibende Werte für $ s $ , die Anzahl der Werte $ s $ so, dass $ s \ neq r $ und $ s \ EQUIV R (\ mod m) $ ist höchstens $ \ lceil p / m \ rceil - 1 $ .

Wie erhalten wir den Begriff $ \ lceil p / m \ RCEIL - 1 $ ?

Answer 1

Wir möchten zeigen, dass $ k_1 \ neq k_2 \ in \ mathbb {z} _P $ dann

$ \ PR \ Limits _ {(a, b) \ in \ mathbb {z yect _p ^ * \ \ times \ mathbb {z ~ \ _p} [AK_1 + B \ EQUIV AK_2 + b \ pmod m] \ le \ frac {1} {m} $ .

Wenn sowohl Zugabe als auch Multiplikation in $ \ Mathbb {z} _P $ vorgeformt sind.

wir fangen an, indem wir zeigen, dass, wenn $ A \ SIM U (z_p ^ *) $ und $ b \ sim u (Z_p) $ dann für alle $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ , $ (AK_1 + B, AK_2 + B) $ ist einheitlich über $ \ {(x, y) \ in \ mathbb {z} _p _p ^ 2 | x \ neq y \} $ (dh $ h (k_1) $ und $ h (k_2) $ sind mit verschiedenen Einträgen gemeinsam über Paare einheitlich, wo die Zufälligkeit über die Wahl der $ H $ ) ist. Dies ist unmittelbar von der Tatsache, dass für alle $ (c_1, c_2) \ in \ mathbb {z ± _p ^ 2 $ mit $ C_1 \ neq c_2 $ , das folgende System von linearen Gleichungen:

$ \ begin {richten *} & AK_1 + B= C_1 \\ & AK_2 + B= C_2 \ end {richten *} $

hat eine eindeutige Lösung über die Variablen $ (A, B) \ in Z_P ^ * \ Times \ MathBB {Z \ \ Male \ MathBB {Z _P $ . Subtrahieren Sie die zweite Gleichung von den ersten Erträgen $ A (k_1-k_2)= C_1-C_2 $ , seit $ k_1-k_2 $ ist ungleich Null, wir können beide Seiten um inverse multiplizieren und $ a= (k_1-k_2) ^ {- 1} (c_1-c_2) $ . Wenn $ c_1 \ neq c_2 $ , ist dies eine nicht null-Lösung für $ A $ , und wir können Extrahieren Sie $ B $ von einem der beiden Gleichungen. Somit für jedes Paar $ (c_1, c_2) $ mit $ c_1 \ neq c_2 $ Es gibt eindeutig $ (A, B) \ in Z_P ^ * \ Times \ MathBB {Z} _P $ so, dass $ \ BIG ( h_ {a, b} (k_1), h_ {a, b} (k_2) \ big)= (c_1, c_2) $ . Dies setzt Ihre erste Frage an.

jetzt, teilen Sie jetzt $ \ Mathbb {z} _P $ in $ \ lceil p / m \ rceil $ Eimer, $ B_1, ..., B_ {l=lceil p / m \ rceil} $ wie folgt: $ b_1={0,1, ..., m-1 \}, b_2={m, m + 1, ..., 2m-1 \} $ , ..., < Span-Klasse="Math-Container"> $ B_L={m \ lfloor p / m \ rfloor, m \ lceil p / m \ rcein + 1, ..., p-1 \} $ . Beachten Sie, dass jeder Eimer außer dem letzten von Größe von Größe $ M $ ist, und keine zwei Elemente in derselben Eimer sind gleichwertiger Modulo $ M $ . Wir schließen daraus, dass die Anzahl der verschiedenen Paare in $ \ {(x, y) \ in \ mathbb {z} _p ^ 2 | x \ neq y \} $ das äquivalent modulo $ m $ ist höchstens $ p (\ lceil P / M \ RCEIL-1) $ , da nach der Auswahl des ersten Elements mit $ \ lceil p / m \ rceil-1 $ überlassen bleibt Elemente zur Auswahl (Sie müssen einen anderen Eimer auswählen, und jeder Eimer bietet höchstens einen Kandidaten). Erinnern Sie sich an das $ \ BIG (H_ {A, B} (K_1), H_ {A, B} (k_2) \ BIG) \ SIM U (\ {(x, y) \ in \ mathbb {z} _p ^ 2 | x \ neq y \}) $ , so können wir endlich abschließen:

$ \ PR \ Limits _ {(A, B) \ in \ mathbb {z} _p ^ * \ \ times \ mathbb {z ~ \ _p \ mathbb {z _p _p} \ Links [H_ {A, b} (k_1)= h_ {a, b} (k_2) \ pmod m \ rechts]=frac {p (\ lceil p / m \ rcein-1)} {p (p-1)} \ le \ frac {1} {m} $

Beachten Sie, dass der Wert von $ A $ den Wert $ 0 $ erlaubt, nur unsere Analyse einfacher leichter, da Jetzt $ \ BIG (H (H (K_1), H (K_2) \ BIG) $ ist gemeinsam einheitlich über $ \ mathbb { Z} _p ^ 2 $ , aber es gibt eine zusätzliche Wahrscheinlichkeit von $ \ frac {1} {p} $ diese $ a= 0 $ und unsere Hashes ist gleichwertig Modulo $ M $ , also müssen wir uns in diesem Fall mit einer $ o (\ frac {1} {m}) $ an der Kollisionswahrscheinlichkeit gebunden.