Cryptography Reference
In-Depth Information
See the discussion of attacks on RSA on pages 176 and 177 for an application
of the above notions, as well as the references to expectation throughout the
text. The above is also of value when discussing such phenomena as the birthday
attack (see pages 252-255).
E.4 The Law of Large Numbers
In the theory of probability, there exist numerous versions of what is called
the “law of large numbers”. What they all essentially say is that if an experi-
ment is performed
n
times for suGciently large
n
, then the difference between
the expected and actual values is very small. One way of describing this math-
ematically is the following.
Law of Large Numbers
If
X
1
,X
2
,...,X
n
are independent random variables, and
X
=
j
=1
X
j
, then
for any
ε>
0,
j
=1
var(
X
j
)
n
2
p
(
|
X/n
−
E
(
X/n
)
|≥
ε
))
≤
,
·
ε
2
where
p
(
|
X/n
−
E
(
X/n
)
|≥
ε
) is the probability that
|
X/n
−
E
(
X/n
)
|≥
ε
.
The law of large numbers can be illustrated using the binomial distribution
theorem. Let
B
n
(
s
) denote the number of heads in
n
independent coin-flipping
trials.
Then
p
=
p
s
=1
/
2,
E
(
B
n
(
s
)) =
n/
2, and var(
B
n
(
s
)) =
n/
4, so if
X
=
B
n
(
s
), then var(
X
)=
j
=1
X
j
=
n/
4, and
1
p
(
|
X/n
−
E
(
X/n
)
|
>ε
))
≤
ε
2
,
4
n
·
→∞
so as
n
, the probability goes to zero. In other words, we may expect that
the number of heads will not be far from
n/
2 if the experiment is performed
enough times.
E.5 Probability and Error Detection
We conclude this appendix with some data concerning probability and error
detection. We are all familiar with power surges and other electro magnetic
disruptions. These types of interference may cause transmission errors, that
is, the loss, alteration, or insertion of data.
Thus, we need mechanisms for
detecting when this occurs.
A simple mechanism for error detection is called
parity checking
, which in-
volves the sender's computation of an additional bit, called a
parity bit
, which
Search WWH ::
Custom Search