Cryptography Reference
In-Depth Information
x
2
Exercise 2.12.6
Let
q
be an odd prime power and
R
(
x
)
∈ F
q
[
x
]. Show
that the expected complexity of finding roots of
R
(
x
) using polynomial factorisation is
O
(log(
q
)
M
(log(
q
))) bit operations.
=
+
ax
+
b
Exercise 2.12.7
Show, using Kronecker substitution, fast versions of Euclid's algorithm
and other tricks, that one can compute one root in
F
q
(if any exist) of a degree
d
polynomial
in
F
q
[
x
] in an expected
O
(log(
qd
)
M
(
d,q
)) bit operations.
2
m
) then, instead of
x
(
q
−
1)
/
2
, one considers the
trace polyno-
When
q
is even (i.e.,
q
=
=
m
−
1
i
=
0
x
2
i
. (A similar idea can be used over any field of small characteristic.)
mial
T
(
x
)
Exercise 2.12.8
Show that the roots of the polynomial gcd(
R
1
(
x
)
,T
(
x
)) are precisely the
α
∈ F
q
such that
R
1
(
α
)
=
=
0 and Tr
F
2
m
/
F
2
(
α
)
0.
∈ F
2
m
[
x
]ofdegree
<d
and then computing gcd(
R
1
(
x
)
,T
(
u
(
x
)))
gives a Las Vegas root-finding algorithm as before. See Section 21.3.2 of [
497
] for details.
Taking random
u
(
x
)
Higher degree factors
Having found the roots in
F
q
one can try to find factors of larger degree. The same ideas
can be used. Let
gcd(
F
(
x
)
/R
1
(
x
)
,x
q
2
gcd(
F
(
x
)
/
(
R
1
(
x
)
R
2
(
x
))
,x
q
3
R
2
(
x
)
=
−
x
)
,R
3
(
x
)
=
−
x
)
,....
Exercise 2.12.9
Show that all irreducible factors of
R
i
(
x
) over
F
q
[
x
]havedegree
i
.
∈ F
q
[
x
]ofdegree
Exercise 2.12.10
Give an algorithm to test whether a polynomial
F
(
x
)
d
is irreducible. What is the complexity?
When
q
is odd, one can factor
R
i
(
x
) using similar ideas to the above, i.e. by computing
gcd(
R
i
(
x
)
,u
(
x
)
(
q
i
−
1)
/
2
−
1)
.
These techniques lead to the
Cantor-Zassenhaus algorithm
. It factors polynomials of
degree
d
over
F
q
in an expected
O
(
d
log(
d
)log(
q
)
M
(
d
)) field operations. For many more
details about polynomial factorisation see Section 7.4 of [
21
], Sections 21.3 and 21.4
of [
497
], Chapter 14 of [
220
], [
332
], Chapter 4 of [
350
,
351
] or Section 4.6.2 of [
308
].
Exercise 2.12.11
Let
d
∈ F
q
[
x
]ofdegree
d
.Given1
<b<n
suppose
we wish to output all irreducible factors of
F
(
x
)ofdegreeatmost
b
. Show that the
expected complexity is
O
(
b
log(
d
)log(
q
)
M
(
d
)) operations in
∈ N
and
F
(
x
)
F
q
. Hence, one can factor
F
(
x
) completely in
O
(
d
log(
d
)log(
q
)
M
(
d
)) operations in
F
q
.
Exercise 2.12.12
Using the same methods as Exercise
2.12.7
, show that one can find an
irreducible factor of degree 1
<b<d
of a degree
d
polynomial in
F
q
[
x
] in an expected
O
(
b
log(
dq
)
M
(
d,q
)) bit operations.
