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
.