Cryptography Reference
In-Depth Information
following.
(1) P(κ[w] ∈T
w
) = 1−
n
w
M
w
τ
(1−p
w
tau
x
).
τ=1
x=1
(2) P(freq
w
= c) =
0
@
1
A
0
1
M
w
τ
r
M
w
r
c
@
A
p
w
τ
r
x
(1−p
w
τ
r
x
′
)
(1−p
w
r
x
)
.
r=1
x=1
x=1
{τ
1
,τ
2
,...,τ
c
}
⊆{1,2,...,n
w
}
x
′
=x
r∈{1,2,...,n
w
}\
{τ
1
,τ
2
,...,τ
c
}
M
w
τ
n
w
(3) E(freq
w
) =
p
w
τ
x
.
τ=1
x=1
Proof: First, we prove item (1). We know that κ[w] ∈ T
w
, if and only if
κ[w] ∈G
w
τ
for all τ ∈{1,...,n
w
}. Again, κ[w] ∈G
w
τ
, if and only if for each
x∈{1,...,M
w
τ
}, κ[w] = g
w
τ
x
, the probability of which is (1−p
w
τ
x
). Hence
the result follows.
Next, we prove item (2). Item (2) is a generalization of item (1), since
P(κ[w] ∈T
w
) = 1−P(freq
w
= 0).
For an arbitrary c, 0 ≤ c ≤ n
w
, κ[w] occurs exactly c times in T
w
, if and
only if it occurs once in exactly c out of n
w
many G
w
's, say once in each of
G
w
τ
1
,G
w
τ
2
,...,G
w
τ
c
, and it does not occur in any of the remaining n
w
−c many
G
w
's. We call such a division of the G
w
's a c-division. Again, for 1 ≤ r ≤ c,
κ[w] occurs exactly once in G
w
τ
r
, if and only if κ[w] equals exactly one of the
M
w
τ
r
members of G
w
τ
r
and it does not equal any of the remaining (M
w
τ
r
−1)
members of G
w
τ
r
. Thus, the probability that κ[w] occurs exactly once in G
w
τ
r
is given by
M
w
τ
r
p
w
τ
r
x
(1−p
w
τ
r
x
′
).
x=1
x
′
=x
Also, for any r ∈ {1,2,...,n
w
}\{τ
1
,τ
2
,...,τ
c
}, κ[w] does not occur in G
w
r
M
wr
n
w
c
with probability
(1 −p
w
r
x
). Adding the contributions of all
many
x=1
c-division's, we get the result.
Finally, we come to item (3). For 1 ≤ τ ≤ n
w
, 1 ≤ x ≤ M
w
τ
let u
τ,x
= 1,
if κ[w] = g
w
τ
x
; otherwise, let u
τ,x
= 0. Thus, the number of occurrences of
κ[w] in T
w
is
M
w
τ
n
w
freq
w
=
u
τ,x
.
τ=1
x=1
