Cryptography Reference
In-Depth Information
Hence
N
!
N
θ
√
N
(
N
1
−
p
=
−
θ
√
N
)!
−
N
+
θ
√
N
1
e
−
θ
√
N
√
N
∼
−
exp
√
N
)log
1
√
N
√
N
=
−
θ
+
(
−
N
+
θ
−
2
2
+
=−
ε
−
ε
2
)
We now use log(1
−
ε
)
o
(
ε
exp
+
θ
√
N
)log
1
−
θ
√
N
√
N
1
−
p
∼
+
(
−
N
−
exp
o
(1)
2
2
+
−
θ
∼
which means it tends towards
e
−
θ
2
.
A simpler way to express the birthday paradox consists of estimating the number
of collisions. If we take a sequence
X
1
,...,
X
n
of independent uniformly distributed
random variables in
{
1
,...,
N
}
, the number of collisions is
n
−
1
n
C
=
1
X
i
=
X
j
i
=
1
j
=
i
+
1
1
N
, so the expected number of collisions is
and we have Pr[
X
i
=
X
j
]
=
n
(
n
−
1)
1
N
E
(
C
)
=
×
2
√
N
,wehave
E
(
C
)
∼
θ
2
2
. The variance is
V
(
C
)
∼
θ
2
2
and for
n
=
θ
as well.
Here, the analysis is quite easy when the
co
mplexity is fixed, but there is no real
need, in practice, for upper-bounding it by
√
N
as in Fig. 3.7. The general analysis is
θ
the subject of Exercise 3.3.
For completeness we provide a similar result which is used in order to find collisions
between two separated lists (for instance, if we want to find a male-female couple of
people with the same birthday).
θ
1
√
N and
θ
2
√
N by picking inde-
Theorem 3.3.
If we make two sequences of length
pendent random numbers in
{
1
,
2
,...,
N
}
with uniform distribution, we get at least
Search WWH ::
Custom Search