8. Klasse Denkaufgabe am Abend Bei der Suche nach der Bestätigungszahl für einen Bitcoin-Block müssen Hashwerte berech-net werden, die eine bestimmte Anzahlnan Nullbits am Anfang des Hashwerts aufweisen.Die Hashwerte selbst sind 160 Bit lang. a) Wie groß ist die Wahrscheinlichkeit, dass der Hashwert für die erste BestätigungszahlbereitsnNullbits am Anfang aufweist? Ich sage, es müssen 2^(n+1) Möglichkeiten betrachtet werden, da ja das n+1 Bit eins sein muss. Also wäre die Wahrscheinlichkeit 1/2^(n+1)
b) Wie viele Bestätigungszahlen muss man ausprobieren, damit ein Hash-Wert mit n=32Nullbits am Anfang mit einer Wahrscheinlichkeit von 50% gefunden ist? Wieviele Versuche braucht man für n=33? Meine Antwort: Gleichung nach x Auflösen 0.5= x * 1/2^(32+1) Lösung lässt sich sofort ablesen: 2^32 Anzahl der Versuche: 0.5= x * 1/2^(33+1) <=> x = 2^33
c) Wie groß ist der Rechenaufwand (in der O-Notation), um einen Hash-Wert mit n Nullbits am Anfang zu finden?
a) Ja, wenn du die Frage richtig verstanden hast. Das nennen wir p(n). b) Wahrscheinlichkeit eines Fehlversuches: 1-p(n) Wahrscheinlich von N Fehlversuchen (1-p(n))^N. Das soll kleiner 50% sein. Dann nach N auflösen c) Rechenaufwand ~ N das Ganze als Funktion von n aufschreiben und in O(n)-Notation überführen 8. Klasse halte ich für ein Gerücht. Bei mir war das damals 11.
Edit: Selbst gemerkt. War Quatsch
A. S. schrieb: > Wahrscheinlichkeit eines Fehlversuches: 1-p(n) > Wahrscheinlich von N Fehlversuchen (1-p(n))^N. Das soll kleiner 50% > sein. Dann nach N auflösen du meinst also: N = log 1-1/2^33 (0,5) = 5954105403? A. S. schrieb: > c) > Rechenaufwand ~ N > das Ganze als Funktion von n aufschreiben und in O(n)-Notation > überführen wie sähe das aus?
Warum sollte man über die Fehlversuche gehen? Warum kommt bei meinem Ansatz eine andere Zahl heruas?
Gast
#6696107
Klaus S. schrieb: > Ich sage, es müssen 2^(n+1) Möglichkeiten betrachtet werden, da ja das > n+1 Bit eins sein muss. Deine Formulierung suggeriert was anderes. Das kann man aber nicht durch diskutieren klären.
Klaus S. schrieb: > Warum sollte man über die Fehlversuche gehen? Warum kommt bei meinem > Ansatz eine andere Zahl heruas? du willst in der Regel nicht wissen, ob du in N Versuchen genau 1 Hash findest, 2 Hashs wären auch okay, oder drei, oder vier, oder? Klaus S. schrieb: > wie sähe das aus? keine Ahnung, definitiv keine Achtklässlermathematik. Am Ende wird aber wohl rauskommen, dass das exponentielle Komplexität hat.
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.