Cryptography Reference
In-Depth Information
repeated factor. It follows that
F
(
x
) is square-free if
F
(
x
)
0 and gcd(
F
(
x
)
,F
(
x
))
=
=
1.
gcd(
F
(
x
)
,F
(
x
)) then
F
(
x
)
/S
(
x
) is square-free.
If
F
(
x
)
∈ F
q
[
x
] and
S
(
x
)
=
Exercise 2.12.1
Determine the complexity of testing whether a polynomial
F
(
x
)
∈ F
q
[
x
]
is square-free.
Exercise 2.12.2
Show that one can reduce polynomial factorisation over finite fields to the
case of factoring square-free polynomials.
Finding roots of polynomials in finite fields
Let
F
(
x
)
∈ F
q
[
x
]havedegree
d
. The roots of
F
(
x
)in
F
q
are precisely the roots of
gcd(
F
(
x
)
,x
q
R
1
(
x
)
=
−
x
)
.
(2.2)
If
q
is much larger than
d
then the efficient way to compute
R
1
(
x
) is to compute
x
q
(mod
F
(
x
)) using a square-and-multiply algorithm and then run Euclid's algorithm.
Exercise 2.12.3
Determine the complexity of computing
R
1
(
x
) in equation (
2.2
). Hence,
explain why the decision problem “Does
F
(
x
)havearootin
F
q
?” has a polynomial-time
solution.
The basic idea of root-finding algorithms is to note that, if
q
is odd,
x
q
−
x
=
x
(
x
(
q
−
1)
/
2
1)(
x
(
q
−
1)
/
2
1). Hence, one can try to split
7
R
1
(
x
) by computing
+
−
gcd(
R
1
(
x
)
,x
(
q
−
1)
/
2
−
1)
.
(2.3)
Similar ideas can be used when
q
is even (see Section
2.14.2
).
Exercise 2.12.4
Show that the roots of the polynomial in equation (
2.3
) are precisely the
α
F
q
.
∈ F
q
such that
F
(
α
)
=
0 and
α
is a square in
To obtain a randomised (Las Vegas) algorithm to factor
R
1
(
x
) completely when
q
is odd
one simply chooses a random polynomial
u
(
x
)
∈ F
q
[
x
]ofdegree
<d
and computes
gcd(
R
1
(
x
)
,u
(
x
)
(
q
−
1)
/
2
−
1)
.
F
q
. In practice,
it suffices to choose
u
(
x
) to be linear. Performing this computation sufficiently many times
on the resulting factors of
R
1
(
x
) and taking gcds (greatest common divisors) eventually
leads to the complete factorisation of
R
1
(
x
).
This computation selects those roots
α
of
R
1
(
x
) such that
u
(
α
) is a square in
Exercise 2.12.5
Write down pseudocode for the above root-finding algorithm and show
that its expected complexity (without using a fast Euclidean algorithm) is bounded by
O
(log(
d
)(log(
q
)
M
(
d
)
d
2
))
O
(log(
q
)log(
d
)
d
2
) field operations.
+
=
7
We reserve the word “factor” for giving the full decomposition into irreducibles, whereas we use the word “split” to mean
breaking into two pieces.
