Cryptography Reference
In-Depth Information
Theorem 15.5.12
Let p be prime and n,b
∈ N
.
n
d
|
n
µ
(
d
)
p
n/d
1
=
=
p
n
/n
+
O
(
p
n/
2
/n
)
where µ
(
d
)
is the Mobius function.
8
1. I
(
n
)
2. If n
1
/
100
≤
≤
n
99
/
100
=
p
n
(
b/n
)
(1
+
o
(1))
n/b
as n tends to infinity.
b
then N
(
n,b
)
3. If n
1
/
100
≤
b
≤
n
99
/
100
then p
(
n,b
)
is at least u
−
u
(1
+
o
(1))
where u
=
n/b and n tends to
infinity.
4. If n
1
/
100
n
99
/
100
≤
b
≤
then the expected number of trials before a randomly chosen
F
p
[
x
]
of degree n is b-smooth is u
u
(1
+
o
(1))
as u
element of
→∞
.
Proof
Statement 1 follows from an elementary counting argument (see, for example,
Theorem 3.25 of Lidl and Niederreiter [
350
]).
Statement 2 in the case
p
2 is Corollary A.2 of Odlyzko [
421
]. The general result
was proved by Soundararajan (see Theorems 2.1 and 2.2 of Lovorn Bender and Pomer-
ance [
358
]). Also see Section 9.15 of [
350
].
Statement 3 follows immediately from statement 2 and the fact there are
p
n
monic
polynomials of degree at most
n
(when considering smoothness it is sufficient to study
monic polynomials). Statement 4 follows immediately from statement 3.
=
The algorithm then follows exactly the ideas of the previous section. Suppose
g
has
prime order
r
(
p
n
|
−
1) and
h
∈
g
. The factor base is
B
={
P
(
x
)
∈ F
p
[
x
]:
P
(
x
) is monic, irreducible and deg(
P
(
x
))
≤
b
}
for some integer
b
to be determined later. Note that #
B
=
I
(1)
+
I
(2)
+···+
I
(
b
)
≈
p
b
+
1
/
(
b
(
p
−
1)) (see Exercise
15.5.14
). We compute random powers of
g
multiplied by
G
(where, if
r
2
(
p
n
1),
G
⊆ F
p
n
is the subgroup of order (
p
n
a suitable
δ
∈
−
−
1)
/r
;
when
r
2
(
p
n
1) then use the method of Exercise
15.5.8
), reduce to polynomials in
F
p
[
x
]ofdegreeatmost
n
and try to factor them into products of polynomials from
|
−
.
By Exercise
2.12.11
the cost of factoring the
b
-smooth part of a polynomial of degree
n
is
O
(
bn
log(
n
)log(
p
)
M
(log(
p
)))
B
O
(log(
p
n
)
3
) bit operations (in any case, polynomial-
time). As previously, we are generating polynomials of degree
n
uniformly at random
and so, by Theorem
15.5.12
, the expected number of trials to get a relation is
u
u
(1
+
o
(1))
where
u
=
=
n/b
as
u
→∞
. We need to obtain #
B
relations in general. Then we obtain
=
P
∈
B
a single relation of the form
hg
a
δ
P
e
P
, perform linear algebra and hence solve
the DLP.
Exercise 15.5.13
Write the above algorithm in pseudocode.
Exercise 15.5.14
Show that
i
=
1
I
(
b
)
1
b
p
b
(1
O
(
bp
b/
2
). Show that a
≤
+
2
/
(
p
−
1))
+
very rough approximation is
p
b
+
1
/
(
b
(
p
−
1)).
8
This is the “prime number theorem for polynomials”,
I
(
n
)
≈
p
n
/
log
p
(
p
n
).
