Cryptography Reference
In-Depth Information
Wir wollen den Umgang mit durch Programmvariablen induzierten Zufallsvariablen
anhand von Beispiel 4.6.1 weiter vertiefen.
Beispiel 4.6.2 (Beispiel 4.6.1 fortgef.). Für den Algorithmus aus Beispiel 4.6.1 gilt zum
Beispiel:
Prob
{A
=1
,b
0
=0
,b
1
=0
,b
2
=0
}
=Prob
{b
0
=0
,b
1
=0
,b
2
=0
,b
3
=0
}
1
16
=
.
Für die Wahrscheinlichkeit, dass
A
das Bit
1
liefert unter der Bedingung, dass
b
0
=0
und
b
1
=0
gilt, erhalten wir
Prob
{
A
=1
|
b
0
=0
,b
1
=0
}
=Prob
{
b
2
=1
oder
(
b
2
=0
,b
3
=0)
|
b
0
=0
,b
1
=0
}
=Prob
{b
2
=1
| b
0
=0
,b
1
=0
}
+
Prob
}
(1
=Prob
{b
2
=1
}
+Prob
{b
2
=0
,b
3
=0
}
=1
/
2+1
/
4
=3
/
4
.
{
b
2
=0
,b
3
=0
|
b
0
=0
,b
1
=0
Dabei gilt (
1
), da die Bits
b
0
,...,b
3
unabhängig voneinander gewählt werden (siehe auch
Aufgabe 4.9.13).
Die Wahrscheinlichkeit, dass
A
das Bit
1
liefert unter der Bedingung, dass
b
0
=
b
1
gilt,
errechnet sich wie folgt:
Prob
{A
=1
| b
0
=
b
1
}
=Prob
{
(
A
=1
,b
0
=1)
oder
(
A
=1
,b
0
=0)
| b
0
=
b
1
}
=Prob
{
A
=1
,b
0
=1
|
b
0
=
b
1
}
+
Prob
{A
=1
,b
0
=0
| b
0
=
b
1
}
(1
=Prob
+
Prob
{b
0
=0
| b
0
=
b
1
}·
Prob
{A
=1
|
0=
b
0
=
b
1
}
=1
/
2+1
/
2
{
b
0
=1
|
b
0
=
b
1
}
·
3
/
4
=7
/
8
,
wobei wir in (
1
) für den zweiten Summanden Lemma 3.3.3 verwenden.
Es sei nun wieder
A
(
x
)
ein zufallsgesteuerter Algorithmus mit maximaler Laufzeit
t
,
so dass in jedem Lauf von
A
(
x
)
die Zuweisung
y
=
flip
(
l
)
genau einmal
ausgeführt
wird. Es sei
c
l
.Mit
A
(
x
)
bezeichnen wir den Algorithmus, der sich aus
Algorithmus
A
(
x
)
ergibt, in dem man die Variable
y
fest auf den Wert
c
setzt, also die
Zuweisung
y
=
flip
(
l
)
durch
y
=
c
ersetzt. Man sieht leicht, dass folgende Aussage für
alle
c
∈{
∈{
0
,
1
}
y
=
c
}
∗
gilt (siehe Aufgabe 4.9.14):
0
,
1
=
c
}
A
(
x
)=
c
|
Prob
{
A
(
x
)
y
=
c
=Prob
{
y
=
c
}
.
(4.6.4)
