Cryptography Reference
In-Depth Information
Zunächst beobachten wir, dass, zum Beispiel,
(
A
b
0
=0
)
b
1
=0
wohldefiniert ist, aber
(
A
b
0
=1
)
b
1
=0
nicht. Insbesondere können wir
A
b
0
=0
,b
1
=0
schreiben. Es gilt:
=
3
4
=Prob
A
Prob
{
b
0
=0
,b
1
=0
=1
}
A
=1
{
|
b
0
=0
,b
1
=0
}
.
Neben durch Programmvariablen induzierte Zufallsvariablen werden wir häufig auch
gänzlich neue Zufallsvariablen auf der Menge der Läufe eines Algorithmus betrachten.
Beispiel 4.6.5. Es sei
B
der Algorithmus, den man aus Algorithmus
A
in Beispiel 4.6.1
erhält, indem man die letzte Zeile durch »gib flip
()
aus« ersetzt. Es bezeichne weiterhin
X
die Zufallsvariable, die für jeden Lauf
α
t
von
B
das Bit liefert, welches
bei Ausführung der letzten Zeile des Algorithmus gewählt wird, wobei
t
die maximale
Laufzeit von
B
bezeichnet. Der Wert von
X
(
α
)
sei
1
, falls im Lauf
α
von
B
die letzte
Zeile nicht ausgeführt wird. Es gilt nun zum Beispiel:
∈{
0
,
1
}
Prob
{
X
=0
}
=Prob
{
b
0
=
b
1
=
b
2
=
b
3
=0
,X
=0
}
1
32
=
.
Weiter gilt:
Prob
{B
=1
| X
=1
}
=
Prob
{
B
=1
,X
=1
}
Prob
{
X
=1
}
29
32
(1
=
−
32
1
=
29
31
,
wobei wir (
1
) wegen
Prob
{
B
=1
,X
=1
}
=Prob
{
b
0
=1
}
+Prob
{
b
0
=0
,b
1
=1
}
+
=
2
+(
2
)
2
+(
2
)
3
+
Prob
{
b
0
=
b
1
=0
,b
2
=1
}
+Prob
{
b
0
=
b
1
=
b
2
=
b
3
=0
,X
=1
}
(
2
)
5
=
2
32
erhalten.
Man beachte, dass
Prob
{B
=1
| X
=1
}
=Prob
{A
=1
}
=
1
16
gilt, was vielleicht
zunächst überraschend ist.
Ein alternativer Wahrscheinlichkeitsraum. Häufig werden wir zufallsgesteuerte
Algorithmen betrachten, in deren Pseudocode selbst nicht weiter spezifizierte zufalls-
gesteuerte Algorithmen genannt werden. Die Laufzeit dieser nicht weiter spezifizierten
Algorithmen wird dabei immer parameterunabhängig durch eine Konstante nach oben be-
schränkt werden können. Des Weiteren wird der Pseudocode Flipoperationen enthalten,
die höchstens einmal ausgeführt werden.
