Herleitung Geburtstagsproblem/Hashkollisionen

Moderator: Einführung in die Kryptographie

arne.lottmann
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Okt 2010 16:25

Herleitung Geburtstagsproblem/Hashkollisionen

Beitrag von arne.lottmann » 8. Feb 2013 14:52

In der Vorlesung wurde die Formel zur Abschätzung der benötigten Anzahl von Menschen für einen doppelten Geburtstag so hergeleitet:
\(q = \prod\limits_{i=1}^{k-1} (1 - \frac{i}{m})\)
\(q \leq \prod\limits_{i=1}^{k-1} e^{-\frac{i}{m}} = e^{-\sum\limits_{i=1}^{k-1} \frac{i}{m}} = e^{-\frac{k(k-1)}{2m}}\)
\(\Rightarrow k \geq (1 + \sqrt{1 + 8m \log(2)}) / 2\)

Kann jemand die fehlenden Schritte zwischen der vorletzten und der letzten Zeile ergänzen? In meinen Versuchen bin ich immer auf folgendes gekommen:
\(k \leq (1 + \sqrt{1 + 8m \log(2)}) / 2\)

ISTler
Erstie
Erstie
Beiträge: 22
Registriert: 3. Mai 2010 12:23

Re: Herleitung Geburtstagsproblem/Hashkollisionen

Beitrag von ISTler » 8. Feb 2013 16:53

\(q \leq e^{-\frac{k(k-1)}{2m}}\)
\(\log(q) \leq -\frac{k(k-1)}{2m}\)
\(-\log(q) \geq \frac{k(k-1)}{2m}\)
\(-2m\log(q) \geq k(k-1)\)
\(2m\log(q^{-1}) \geq k^2-k\)
\(0 \geq k^2-k-2m\log(q^{-1})\)

EDIT: Falsch gedacht, kommt das falsche raus.
EDIT2: Ich hab nochmal länger nachgedacht und auch gegoogelt. Eigentlich müsste die Ungleichung wirklich anders herum sein.
Wenn man statt \(1 + x \leq e^x\) das ungefähre \(1 + x \approx e^x\) nimmt (x bleibt ja zwischen 0 und deutlich über -1) kann man das Ganze richtig biegen.
Ich hab eben nochmal in die Hausübung geschaut. Ich habe sie analog zum Buch gemacht. Die Korrekteurin hat mir dann aber alle Ungleichungen umgedreht.

Antworten

Zurück zu „Einführung in die Kryptographie“