Cryptography Reference
In-Depth Information
We obtain
z
k n
k
p c
t k 1 (1
t ) n k dt
max
A
|
p 0 |≤
(4.1)
1
2
and thus
z
max
t
k n
k
1] t k 1 (1
t ) n k .
1
2
p c
|
p 0 |≤
[0
,
k
1
n 1 ; hence,
=
The maximum is obtained for t
z
( k
k n
k
1) k 1 ( n
k ) n k
1
2
p c
|
p 0 |≤
.
( n
1) n 1
2 k 1
n 1
2
n 1
2
Let x
=
n 1
1. We have k
1
=
(1
+
x ) and n
k
=
(1
x ). We have
0
x
1 and
z
1
k n
k
2 n 1 (1
x ) 1 x
1
2
n 1
2
p c
x ) 1 + x (1
|
p 0 |≤
+
.
k 1 and the Stirling approximation, we obtain that this
bound is asymptotically equal to θ n
n n 1
Note that by using k k =
and so the bound we want to prove is not so
2 π
loose.
2 2 x 2 . Hence,
+
x ) 1 + x (1
x ) 1 x
We can easily prove that (1
z
1
2 n 1 2 ( n 1) x 2
k n
k
1
2
p c
|
p 0 |≤
.
θ
1
n
θ +
1
+
θ +
n 1 +
n 1 =
Since k
1
( n
1) z
z ,wehave x
. Thus,
n 1
k n
k
1
2 n
2 ( n θ + 1) 2
p c
|
p 0 |≤ θ ×
×
.
n
1
3, we have k k 2 n
3
For n
=
4 ; thus,
θ n
1
2 3 ×
3
4 ×
2 (3 θ + 1) 2
p c
|
p 0 |≤
2
×
.
n 1
θ n and this remains true even for
1
p c
1
For
θ
2 3 , we obtain
|
p 0 |≤
2
θ>
2 3 .We
now concentrate on n
4.
 
Search WWH ::




Custom Search