That means the latin square cryptographic system achieves perfect secrecy if each key is used with the same probability
3
Байду номын сангаас
b = amodb
This average bit complexity O n Thus the average bit complexity of The Euclidean Algorithm is O (n2)
3 EXERCISE 1 IN BOOK Introducing to Algorithms
=
0
Pr [9|N ]
=
Pr [9,N ] Pr [N]
=
2 15
pr [D|9]
=
Pr [9,D] Pr [8]
=
0
pr
[N |9]
=
Pr [9,N ] Pr [9]
=
1
Pr
[10, D]
=
1 36
Pr
[10, N ]
=
2 36
=
1 18
Pr
[10|D ]
=
Pr [10,D] Pr [D]
=
1 6
Pr
[6|D ]
=
Pr [6,D] Pr [D]
=
1 6
pr
[D |6]
=
Pr [6,D] Pr [6]
=
1 5
Pr [6|N ]
=
Pr [6,N ] Pr [N]
=
2 15
pr
[N |6]
=
Pr [6,N ] Pr [6]
=
4 5
Pr [7, D]
=
0 36
=0
Pr
[7, N ]
=
6 36
=
1 6
=0
Pr
[3, N ]
=
2 36
=
1 18
Pr
[3|D ]
=
Pr [3,D] Pr [D]
=
0
Pr [3|N ]
=
Pr [3,N ] Pr [N]
=
1 15
Pr
[D |3]
=
Pr [3,D] Pr [3]
=
0
Pr
[N |3]
=
Pr [3,N ] Pr [3]
=
1
Pr
[4, D]
=
1 36
Pr
[4, N ]
Pr
[2, D]
=
1 36
Pr
[2, N ]
=
0 36
=
0
Pr
[2|D ]
=
Pr [2,D] Pr [D]
=
1 6
Pr [2|N ]
=
Pr [2,N ] Pr [N]
=
1 6
Pr
[D |2]
=
Pr [2,D] Pr [2]
=
1
Pr
[N
|2]
=
Pr [2,N ] Pr [2]
=
0
Pr [3, D]
=
0 36
1
=
n
· Pr
K ∈K
[x
=
dk (y)]
1 =
n
on the other hand
Pr [y = y | x = x] = Pr [K = ki ]
in which
ki ∈ {k | y = ek (x)}
thus
1 Pr [y = y | x = x] = Pr [K = ki ] = n
According to Bayes theorem
=
1 6
pr
[D |8]
=
Pr [8,D] Pr [8]
=
1 5
Pr [8|N ]
=
Pr [8,N ] Pr [N]
=
2 15
pr
[N |8]
=
Pr [8,N ] Pr [8]
=
4 5
Pr [9, D]
=
0 36
=0
Pr
[9, N ]
=
4 36
=
1 9
Pr
[9|D ]
=
Pr [9,D] Pr [D]
plain text x
appears with probability pi , As is known, Pr [K = ki ] =
1 n
thus ∀x
∈P
and ∀y
∈C:
Pr [y = y] = Pr [K = K ]Pr [x = dk (y)]
K ∈K
1 = K ∈K n Pr [x = dk (y)]
=
0
Pr
[11|N ]
=
Pr [11,N ] Pr [N]
=
1 15
pr
[D |11]
=
Pr [11,D] Pr [11]
=
0
pr
[N |11]
=
Pr [11,N ] Pr [11]
=
1
2
Pr
[12, D]
=
1 36
Pr
[12, N ]
=
0 36
=
0
Pr
[12|D ]
=
Pr [12,D] Pr [D]
2 | 24
2 | 14
Thus:
2 | 24s + 14t
But it is not true that 2|1
So there is no s and t that 24s + 14t = 1
2 EXERCISE 2
According to Theorem of Dr.Finck, The Euclidean algorithm will find gcd(a, b) after a cost of
at most l og2M ax(a, b) +1 integer divisions. Both a and b are n −bi t positive integers. thus
we have:
2n−1 ≤ a < 2n
2n−1 ≤ b < 2n
1
Thus The Euclidean algorithm has complexity of O (l og22n) = O (n) Considering in each step of The Euclidean algorithm, the main process is
pr
[D |10]
=
Pr [10,D] Pr [10]
=
1 3
Pr
[10|N ]
=
Pr [10,N ] Pr [N]
=
1 15
pr
[N |10]
=
Pr [10,N ] Pr [10]
=
2 3
Pr [11, D]
=
0 36
=0
Pr
[11, N ]
=
2 36
=
1 18
Pr
[11|D ]
=
Pr [11,D] Pr [D]
Pr [x = x | y = y] · Pr [y = y] = Pr [y = y | x = x] · Pr [x = x]
We already known that So we’ve got that
1 Pr [y = y] = n = Pr [y = y | x = x]
Pr [x = x] = Pr [x = x | y = y]
=
2 36
=
1 18
Pr
[4|D ]
=
Pr [4,D] Pr [D]
=
1 6
pr [D|4]
=
Pr [4,D] Pr [4]
=
1 3
Pr [4|N ]
=
Pr [4,N ] Pr [N]
=
1 15
pr
[N |4]
=
Pr [4,N ] Pr [4]
=
2 3
Pr [5, D]
=
0 36
=0
Pr
[5, N ]
=
1 6
Pr
[12|N ]
=
Pr [12,N ] Pr [N]
=
0
pr
[D |12]
=
Pr [12,D] Pr [12]
=
1
pr
[N |12]
=
Pr [12,N ] Pr [12]
=
0
4 EXERCISE 2 IN BOOK Introducing to Algorithms
Proof. First, we define the cryptographic mechanism as (P , K , C , E , D) and assume that
Pr
[7|D ]
=
Pr [7,D] Pr [D]
=
0
Pr [7|N ]
=
Pr [7,N ] Pr [N]
=
1 5
pr [D|7]
=
Pr [7,D] Pr [7]
=
0
pr
[N |7]
=
Pr [7,N ] Pr [7]
=
1
Pr
[8, D]
=
1 36
Pr
[8, N ]
=
4 36
=