Cryptography Reference
In-Depth Information
where f ( X )
g ( X ) means lim X →∞ f ( X ) /g ( X )
=
1. A crude estimate for ρ ( u ), as u
→∞
1 /u u . For further details and references see Section 1.4.5 of [ 150 ].
The following result of Canfield, Erd os and Pomerance [ 110 ] is the main tool in this
subject. This is a consequence of Theorem 3.1 (and the corollary on page 15) of [ 110 ].
is ρ ( u )
Theorem
)log( N ) / log(log( N )) . Then there is a constant c (that does not depend on u)such
that
15.1.2 Let N
∈ N
. Let ,u
∈ R
be such that > 0 and 3
u
(1
( N,N 1 /u )
=
N exp(
u (log( u )
+
log(log( u ))
1
+
(log(log( u ))
1) / log( u )
+
E ( N,u )))
(15.1)
c (log(log( u )) / log( u )) 2 .
where
|
E ( N,u )
|≤
the notation be as in Theorem 15.1.2 . Then ( N,N 1 /u )
Corollary
15.1.3 Let
=
Nu u + o ( u )
Nu u (1 + o (1)) uniformly as u
=
→∞
andu
(1
)log( N ) / log(log( N )) (and
hence also N
→∞
).
Exercise 15.1.4 Prove Corollary 15.1.3 .
[Hint: Show that the expression inside the exp in equation ( 15.1 )isoftheform
u log( u )
+
o ( u )log( u ).]
We will use the following notation throughout the topic.
Definition 15.1.5 Let 0
a
1 and c
∈ R > 0 .The subexponential function for the param-
eters a and c is
exp( c log( N ) a log(log( N )) 1 a ) .
L N ( a,c )
=
log( N ) c (polynomial) while taking a
Note that taking a
=
0gives L N (0 ,c )
=
=
1gives
N c (exponential). Hence, L N ( a,c ) interpolates exponential and polynomial
growth. A complexity O ( L N ( a,c )) with 0 <a< 1 is called subexponential .
L N (1 ,c )
=
Lemma 15.1.6 Let 0 <a< 1 and 0 <c.
1. L N ( a,c ) m
∈ R > 0 .
2. Let 0 <a 1 ,a 2 < 1 and 0 <c 1 ,c 2 . Then, where the term o (1) is as N
=
L N ( a,mc ) for m
→∞
,
L N ( a 1 ,c 1 +
o (1))
if a 1 >a 2 ,
L N ( a 1 ,c 1 )
·
L N ( a 2 ,c 2 )
=
L N ( a 1 ,c 1 +
c 2 )
if a 1 =
a 2 ,
L N ( a 2 ,c 2 +
o (1))
if a 2 >a 1 .
3.
O ( L N ( a 1 ,c 1 ))
if a 1 >a 2 ,
L N ( a 1 ,c 1 )
+
L N ( a 2 ,c 2 )
=
O ( L N ( a 1 , max
{
c 1 ,c 2 }+
o (1)))
if a 1 =
a 2 ,
O ( L N ( a 2 ,c 2 ))
if a 2 >a 1 .
Search WWH ::




Custom Search