Many algorithms for factoring polynomials over finite fields include the following three stages: •
Square-free factorization •
Distinct-degree factorization •
Equal-degree factorization An important exception is
Berlekamp's algorithm, which combines stages 2 and 3.
Berlekamp's algorithm Berlekamp's algorithm is historically important as being the first factorization algorithm which works well in practice. However, it contains a loop on the elements of the ground field, which implies that it is practicable only over small finite fields. For a fixed ground field, its
time complexity is polynomial, but, for general ground fields, the complexity is exponential in the size of the ground field.
Square-free factorization The algorithm determines a
square-free factorization for polynomials whose coefficients come from the finite field
Fq of order with
p a prime. This algorithm firstly determines the
derivative and then computes the gcd of the polynomial and its derivative. If it is not one then the gcd is again divided into the original polynomial, provided that the derivative is not zero (a case that exists for non-constant polynomials defined over finite fields). This algorithm uses the fact that, if the derivative of a polynomial is zero, then it is a polynomial in
xp, which is, if the coefficients belong to
Fp, the
pth power of the polynomial obtained by substituting
x by
x1/
p. If the coefficients do not belong to
Fp, the
pth root of a polynomial with zero derivative is obtained by the same substitution on
x, completed by applying the inverse of the
Frobenius automorphism to the coefficients. This algorithm works also over a field of
characteristic zero, with the only difference that it never enters in the blocks of instructions where
pth roots are computed. However, in this case,
Yun's algorithm is much more efficient because it computes the greatest common divisors of polynomials of lower degrees. A consequence is that, when factoring a polynomial over the integers, the algorithm which follows is not used: one first computes the square-free factorization over the integers, and to factor the resulting polynomials, one chooses a
p such that they remain square-free modulo
p.
Algorithm:
SFF (Square-Free Factorization)
Input: A
monic polynomial f in
Fq[
x] where
q =
pm Output: Square-free factorization of
f R ← 1 # Make
w be the product (without multiplicity) of all factors of
f that have # multiplicity not divisible by
p c ←
gcd(
f,
f′)
w ←
f/
c # Step 1: Identify all factors in
w i ← 1
while w ≠ 1
do y ←
gcd(
w,
c)
fac ←
w /
y R ←
R ·
faci w ←
y;
c ←
c /
y;
i ←
i + 1
end while #
c is now the product (with multiplicity) of the remaining factors of
f # Step 2: Identify all remaining factors using recursion # Note that these are the factors of
f that have multiplicity divisible by
p if c ≠ 1
then c ←
c1/
p R ←
R·
SFF(
c)
p end if Output(
R) The idea is to identify the product of all irreducible factors of
f with the same multiplicity. This is done in two steps. The first step uses the formal derivative of
f to find all the factors with multiplicity not divisible by
p. The second step identifies the remaining factors. As all of the remaining factors have multiplicity divisible by
p, meaning they are powers of
p, one can simply take the
pth square root and apply recursion.
Example of a square-free factorization Let : f = x^{11} + 2 x^9 + 2x^8 + x^6 + x^5 + 2x^3 + 2x^2 +1 \in \mathbf{F}_3[x], to be factored over the field with three elements. The algorithm computes first : c = \gcd(f, f') = x^9 + 2x^6 + x^3 + 2. Since the derivative is non-zero we have and we enter the while loop. After one loop we have , and with updates , and . The second time through the loop gives , , , with updates , and . The third time through the loop also does not change . For the fourth time through the loop we get , , , with updates , and . Since
w = 1, we exit the while loop. Since , it must be a perfect cube. The cube root of , obtained by replacing by is , and calling the square-free procedure recursively determines that it is square-free. Therefore, cubing it and combining it with the value of to that point gives the square-free decomposition : f= (x+1)(x^2+1)^3(x+2)^4.
Distinct-degree factorization This algorithm splits a square-free polynomial into a product of polynomials whose irreducible factors all have the same degree. Let of degree be the polynomial to be factored.
Algorithm Distinct-degree factorization(DDF)
Input: A monic square-free polynomial
Output: The set of all pairs , such that has an irreducible factor of degree and is the product of all monic irreducible factors of of degree .
Begin i:=1;\qquad S:=\emptyset,\qquad f^*:=f;
while \deg f^*\ge 2i
do g=\gcd(f^*, x^{q^i}-x)
if ,
then S:=S\cup\{(g,i)\}; f^*:=f^*/g
end if end while;
if f^*\ne 1,
then S:= S\cup\{(f^*,\deg f^*)\};
if S=\emptyset,
then return ,
else return End The correctness of the algorithm is based on the following:
Lemma. For
i ≥ 1 the polynomial : x^{q^i}-x \in \mathbf{F}_q[x] is the product of all monic irreducible polynomials in
Fq[
x] whose degree divides
i. At first glance, this is not efficient since it involves computing the GCD of polynomials of a degree which is exponential in the degree of the input polynomial. However, : g=\gcd \left (f^*, x^{q^i}-x \right ) may be replaced by : g=\gcd \left (f^*, \left (x^{q^i}-x \mod f^* \right ) \right ). Therefore, we have to compute: : x^{q^i}-x \mod f^*, there are two methods:
Method I. Start from the value of : x^{q^{i-1}}\mod f^* computed at the preceding step and to compute its
qth power modulo the new
f*, using
exponentiation by squaring method. This needs :O \left (\log(q) \deg(f)^2 \right ) arithmetic operations in
Fq at each step, and thus :O \left (\log(q) \deg(f)^3 \right ) arithmetic operations for the whole algorithm.
Method II. Using the fact that the
qth power is a linear map over
Fq we may compute its matrix with : O \left (\deg(f)^2(\log(q)+\deg(f)) \right ) operations. Then at each iteration of the loop, compute the product of a matrix by a vector (with
O(deg(
f)2) operations). This induces a total number of operations in
Fq which is : O \left (\deg(f)^2 (\log(q)+\deg(f)) \right ). Thus this second method is more efficient and is usually preferred. Moreover, the matrix that is computed in this method is used, by most algorithms, for equal-degree factorization (see below); thus using it for the distinct-degree factorization saves further computing time.
Equal-degree factorization Cantor–Zassenhaus algorithm In this section, we consider the factorization of a monic squarefree univariate polynomial
f, of degree
n, over a finite field
Fq, which has pairwise distinct irreducible factors f_1,\ldots,f_r each of degree
d. We first describe an algorithm by Cantor and Zassenhaus (1981) and then a variant that has a slightly better complexity. Both are probabilistic algorithms whose running time depends on random choices (
Las Vegas algorithms), and have a good average running time. In next section we describe an algorithm by Shoup (1990), which is also an equal-degree factorization algorithm, but is deterministic. All these algorithms require an odd order
q for the field of coefficients. For more factorization algorithms see e.g. Knuth's book
The Art of Computer Programming volume 2.
Algorithm Cantor–Zassenhaus algorithm.
Input: A finite field
Fq of odd order
q. A monic square free polynomial
f in
Fq[
x] of degree
n =
rd, which has
r ≥ 2 irreducible factors each of degree
d Output: The set of monic irreducible factors of
f. Factors := {
f};
while Size(Factors)
q[
x] with deg(
h) g:=h^{\frac{q^d-1}{2}}- 1 \pmod f
for each u in Factors with deg(
u) >
d do if gcd(
g,
u) ≠ 1 and gcd(
g,
u) ≠
u,
then Factors:= Factors\,\setminus\, \{u\}\cup\{(\gcd(g,u),u/\gcd(g,u))\};
endif endwhile return Factors The correctness of this algorithm relies on the fact that the ring
Fq[
x]/
f is a direct product of the fields
Fq[
x]/
fi where
fi runs on the irreducible factors of
f. As all these fields have
qd elements, the component of
g in any of these fields is zero with probability : \frac{q^d-1}{2q^d} \sim \tfrac{1}{2}. This implies that the polynomial gcd(
g,
u) is the product of the factors of
g for which the component of
g is zero. It has been shown that the average number of iterations of the while loop of the algorithm is less than 2.5 \log_2 r, giving an average number of arithmetic operations in
Fq which is O(dn^2\log(r)\log(q)). In the typical case where
dlog(
q) >
n, this complexity may be reduced to : O(n^2(\log(r)\log(q)+n)) by choosing
h in the kernel of the linear map : v \to v^q-v \pmod f and replacing the instruction : g:=h^{\frac{q^d-1}{2}}- 1 \pmod f by : g:=h^{\frac{q-1}{2}}- 1 \pmod f. The proof of validity is the same as above, replacing the direct product of the fields
Fq[
x]/
fi by the direct product of their subfields with
q elements. The complexity is decomposed in O(n^2\log(r)\log(q)) for the algorithm itself, O(n^2(\log(q)+n)) for the computation of the matrix of the linear map (which may be already computed in the square-free factorization) and
O(
n3) for computing its kernel. It may be noted that this algorithm works also if the factors have not the same degree (in this case the number
r of factors, needed for stopping the while loop, is found as the dimension of the kernel). Nevertheless, the complexity is slightly better if square-free factorization is done before using this algorithm (as
n may decrease with square-free factorization, this reduces the complexity of the critical steps).
Victor Shoup's algorithm Like the algorithms of the preceding section,
Victor Shoup's algorithm is an equal-degree factorization algorithm. Unlike them, it is a
deterministic algorithm. However, it is less efficient, in practice, than the algorithms of preceding section. For Shoup's algorithm, the input is restricted to polynomials over prime fields
Fp. The worst case
time complexity of Shoup's algorithm has a factor \sqrt{p}. Although exponential, this complexity is much better than previous deterministic algorithms (Berlekamp's algorithm) which have as a factor. However, there are very few polynomials for which the computing time is exponential, and the average time complexity of the algorithm is polynomial in d\log(p), where is the degree of the polynomial, and is the number of elements of the ground field. Let
g =
g1 ...
gk be the desired factorization, where the
gi are distinct monic irreducible polynomials of degree
d. Let
n = deg(
g) =
kd. We consider the
ring R =
Fq[
x]/
g and denote also by
x the image of
x in
R. The ring
R is the direct product of the fields
Ri =
Fq[
x]/
gi, and we denote by
pi the natural
homomorphism from the
R onto
Ri. The
Galois group of
Ri over
Fq is cyclic of order
d, generated by the
field automorphism u →
up. It follows that the roots of
gi in
Ri are : p_i(x), p_i(x^q), p_i \left (x^{q^2} \right ), \ldots, p_i \left (x^{q^{d-1}} \right ). Like in the preceding algorithm, this algorithm uses the same
subalgebra B of
R as the
Berlekamp's algorithm, sometimes called the "Berlekamp subagebra" and defined as : \begin{align} B &= \left \{\alpha \in R \ : \ p_1(\alpha), \cdots, p_k(\alpha) \in \mathbf{F}_q \right \} \\ &= \{u\in R \ : \ u^q=u\} \end{align} A subset
S of
B is said a
separating set if, for every 1 ≤
i p_i(s) \ne p_j(s). In the preceding algorithm, a separating set is constructed by choosing at random the elements of
S. In Shoup's algorithm, the separating set is constructed in the following way. Let
s in
R[
Y] be such that :\begin{align} s&=(Y-x) \left (Y-x^q \right )\cdots \left (Y-x^{q^{d-1}} \right ) \\ &=s_0+\cdots+s_{d-1}Y^{d-1}+Y^d \end{align} Then \{s_0,\dots ,s_{d-1}\} is a separating set because p_i(s)=g_i for
i =1, ...,
k (the two monic polynomials have the same roots). As the
gi are pairwise distinct, for every pair of distinct indexes (
i,
j), at least one of the coefficients
sh will satisfy p_i(s_h)\ne p_j(s_h). Having a separating set, Shoup's algorithm proceeds as the last algorithm of the preceding section, simply by replacing the instruction "choose at random
h in the kernel of the linear map v \to v^q-v \pmod f" by "choose
h +
i with
h in
S and
i in {1, ...,
k−1}". == Time complexity ==