Berechnung kryp. Hashfunktionen und Wahrscheinlichkeit

Ich hänge grade an der 1866 Klausur um 11 Sep 2010 an folgender Frage:

Gegeben sei eine kryp. Hashfunktion h:{0,1}* --> {0,1,2,3} sowie eine Nachricht M mit h(M)=2
Reicht es aus 3 weitere Nachrichten zu würfeln damit die Wahrscheinlichkeit min 38/64 (etwa 60%) mindestens eine dieser Nachrichten ebendalls den Hashwert 2 hat?


Wie berechnet man sowas?

Die Wahrscheinlichkeit dass h einen Hashwert 2 liefert ist 1/4.
Die Wahrscheinlichkeit dass h nicht den Hashwert 2 liefert ist 3/4.
Die Wahrscheinlichkeit das h beim 2.ten Würfel nicht den Hashwert 2 liefert ist 3/4 x 3/4.
Also mit jedem weiterem würfeln wird der Wert kleiner.
Jetzt wird n gesucht so dass 3/4 hoch n > 38/64. Jetzt ein wenig Logarithmus und Potenzrechnen.
n x log (3/4) > log (38/64) <=> n = log(38/64) / log (3/4) <=> n = 1,8121
Bei 1,8121 mal würfeln ist die Wahrscheinlichkeit min 38/64 dass eine der Nachrichten den Hashwert 2 hat. Also reicht es aus 3 weitere Nachrichten zu würfeln.

So htte ich das jetzt berechnet -- ob das richtig ist ???? Kann ich leider nicht sagen....

Hey Danke erstmals.

Aber wenn ich mir die alten Klausurdeckblätter anschaue ist ein Taschenrechner nicht gestattet, als wie komme ich ohne Taschenrechner auf das Ergebnis?

Gruß
Matze

mein Vorgehen wäre wie folgt:
Wahrscheinlichkeit das Haswert h(m) = 2 ist -> 1/4
Wahrscheinlichkeit das Haswert h(m) != 2 ist -> 3/4

Jetzt ist gefragt, dass mindestens einer der nächsten Drei Würfe ebenfalls den Hashwert hat,
also das z.B. Wurf 3 den Hastwert 2 hat:

3/4 * 3/4 * 1/4 = 9/64 ~14%

Also wäre meine Lösung:
Nein es reicht nicht aus, da die Wahrscheinlichkeit aus 3 Würfen mind. in einer den h(m) = 2 zu bekommen ca. 14% beträgt.

Aber ob das stimmt, weiss ich leider auch nicht.

Ist es nicht so dass ich bei jedem Wurf eine Wahrscheinlichkeit von 25% habe eine 2 zu erhalten. Da es egal ist wann die zwei in den nächsten 3 Würfen kommt rechne ich einfach 3x25% und komme auf 75%?

JonesJoker schrieb:

Ist es nicht so dass ich bei jedem Wurf eine Wahrscheinlichkeit von 25% habe eine 2 zu erhalten. Da es egal ist wann die zwei in den nächsten 3 Würfen kommt rechne ich einfach 3x25% und komme auf 75%?

Zum Vergrößern anklicken....

Und wenn Du fünfmal würfelst, beträgt die Wahrscheinlichkeit 125%?

Viele Grüße
Frank

Ups, totale Hirnblockade. Um zu berechnen ob ein Ereignis irgendwann bei 3 Versuchen eintrifft zieht man von 1 die Wahrscheinlichkeit ab dass es 3 mal nicht eintrifft-->1-3/4*3/4*3/4=37/64

Ich würde es auch wie @heiko01 berechnen. Siehe hierzu Aufgabe in EA2.

Ohne Taschenrechner könnte ich (3/4)^n =< 38/64 nicht rechnen. Man könnte die Aufgabe aber so lösen: 3/4 sind 0,75, also 75% (Wahrscheinlichkeit, dass 1. Wurf keine 2 ist). 0,75^2 ist auf jeden Fall kleiner als 0,75: (3/4)^2 = 9/16. Das kann man auch ohne Taschenrechner ausrechnen: 0,5... Bei 2 Würfen sinkt die Wahrscheinlichkeit schon auf rund 50%, die unter den geforderten 60% liegen.

An dieser Aufgabe hänge ich auch fest. Der Weg von Glücksritter klingt eigentlich gut. 3/4*3/4*1/4 wäre "3 weitere und genau 1 Wurf ist 2". Mich verwirrt an der Stelle "mindestens".
Ein weiterer Vorschlag (!):
3 weitere Würfe und keine 2: 3/4*3/4*3/4 = 27/64 =42%
Das Komplementär dazu: 1-27/64 = 37/64 = 58%
Die Lösung Nein ist aber wohl das sichere Ergebnis in dieser Aufgabe 😉))

Nein, 3 Würfe reichen nicht aus. Der Berechnungsweg von @heiko01 und mir entsprechen dem Vorgehen in KE2, S. 83 (Geburtstagsparadoxon), und EA2, Aufgabe 5a. Allerdings haben wir einen Fehler gemacht.

Es geht um schwache Kollisionsresistenz: Nachricht 1 ist gegeben, eine weitere Nachricht 2 wird gesucht, damit gilt: H(1) = H(2). Die Berechnung dafür ist:
((mögliche Ereignisse, dass Ereignis nicht positiv ist - positive Ereignisse)*/mögliche Ereignisse)^n <= gesuchte Wahrscheinlichkeit.

* 3 von 4 Ereignissen treffen nicht zu. Mit jeder Wiederholung sinkt die Wahrscheinlichkeit (p), dass die Ereignisse NICHT zutreffen.
1. Wurf: p = 3/4 (75%), dass h(M) != 2. | (1-p = 25% -> h(M) = 2)
2. Wurf: p = (3/4)^2 (56%), dass h(M) != 2. | (1-p = 44% -> h(M) = 2)
3. Wurf: p = (3/4)^3 (42%), dass h(M) != 2. | (1-p = 58% -> h(M) = 2)
4. Wurf: p = (3/4)^4 (32%), dass h(M) != 2. | (1-p = 68% -> h(M) = 2)

Die Wahrscheinlichkeit soll nun mind. 60 Prozent betragen, dass eine der 3 Nachrichten h(M) = 2 hat. D.h. die Wahrscheinlichkeit, dass h(M) keine 2 ist soll mind. 40% betragen (1-p).

Daher darf in der Gleichung:
(3/4)^n =< gesuchte p
nicht 38/64 (60%) als gesuchte p genommen werden, sondern 26/64 (40%).

(3/4)^n =< 26/64 -> log(26/64) / log(3/4) = 3,13 Würfe.

Ohne Taschenrechner könnte man das einfach prüfen - ganz ohne Log:
(3/4)^3 = 27/64 > 26/64.