Factoring Polynomials in 𝔽_{p}[X]

Andrei Jorza

March 1, 2005

1 Generalities

We will denote by I_{n} the set of irreducible (monic) polynomials of degree n in 𝔽_{p}[X]. There are a few questions. Is I_{n} nonempty? Can one test whether f ∈ I_{n}? Is there is fast algorithm to decompose a (random) polynomial in 𝔽_{p}[X] into irreducible factors?

Proposition 1.1. Let f ∈ 𝔽_{p}[X] be an irreducible polynomials of degree n. Then f(X) | X^{p^{n}} − X and f(X) ∤ X^{p^{m}} − X for any m < n.

Proof. We can realize 𝔽_{p^{n}} as 𝔽_{p}[X]/(f) so f has a root in 𝔽_{p^{n}}, which in turn is a root of X^{p^{n}} − X. Therefore (f(X), X^{p^{n}} − X) ≠ 1 in 𝔽_{p^{n}}[X] and so in 𝔽_{p}[X]. Since f(X) is irreducible over 𝔽_{p}[X] this implies that f(X) | X^{p^{n}} − X.

Assume that f(X) | X^{p^{m}}−X for some m. Then f has a root α in 𝔽_{p^{m}}, since 𝔽_{p^{m}} is the set of roots of X^{p^{m}} −X. Then 1, α, …, α^{m} are m+1 vectors in the m-dimensional vector space 𝔽_{p^{m}}/𝔽_{p}. Therefore they are linearly dependent. Therefore the minimal polynomial g(X) of α in 𝔽_{p}[X] will have degree m < n, which contradicts the fact that f(X) is irreducible.

Theorem 1.2. Let n ≥ 2 be a positive integer. Then

X^{p^{n}} − X = ∏_{d|n} ∏_{f∈I_{d}} f.

Proof. For every d | n and every f ∈ I_{d} we know that f(X) | X^{p^{d}} − X | X^{p^{m}} − X (because X^{p^{n}} − X is Mersenne). Since all the polynomials f are irreducible so coprime, their product will divide X^{p^{n}} − X.

Corollary 1.3. Let a_{n} = |I_{n}|. Then

a_{n} ≥ \frac{p^{n} − (log n)p^{n/2}}{n} .

Proof. By degree comparison, Theorem 1.2 gives p^{n} = ∑_{d|n} da_{d}. By the Möbius inversion formula we get that

a_{n} = \frac{1}{n} ∑_{d|n} p^{d}μ(n/d).

If n = p_{1}^{n_{1}} ⋯ p_{k}^{n_{k}} then a_{n} ≥ \frac{1}{n}(p^{n} − ∑_{1}^{k} p^{n/p_{i}}) ≥ \frac{1}{n}(p^{n} − kp^{n/2}).

In conclusion I_{n} is nonempty for all n ≥ 2.

2 Irreducibility Testing

2.1 Theory

Let f ∈ 𝔽_{p}[X] be a polynomial of degree n. We would like to devise a test to see if f ∈ I_{n}. We have seen that if f is irreducible then f(X)|X^{p^{n}} − X and for all m < n (f(X), X^{p^{m}} − X) = 1. Evidently, a counterexample to this would have m|n so it is enough to check this condition for m = n/p_{i} for each prime divisor p_{i} of n. Let’s make things formal

Theorem 2.1. f ∈ I_{n} if and only if

1. f(X)|X^{p^{n}} − X.

2. For each p_{i} | n a prime divisor we have (f(X), X^{p^{m}} − X) = 1 for m = n/p_{i}.

Proof. Assume that f is irreducible. Then f will pass the test by what we have already seen. Assume that f = f_{1}^{ℓ_{1}} ⋯ f_{r}^{ℓ_{r}}. If ℓ_{j} > 1, then f_{i}^{2} | f cannot divide X^{p^{n}} − X since this polynomial is a product of distinct irreducible polynomials. So ℓ_{i} = 1 for all i.

Let α be a root of f_{1}. If r ≠ 1 then deg f_{1} < n so α has degree < n over 𝔽_{p}. Moreover, if f passes test 1 then α ∈ 𝔽_{p^{n}} so 𝔽_{p^{n}}/𝔽_{p}(α)/𝔽_{p} is a field extension tower. Therefore deg α | n so deg α | n/p_{i} for some i. Then f_{1} | X^{p^{n/p_{i}}} −X so test 2 fails.

2.2 Running Time

The first test is X^{p^{n}} ≡ X (mod f(X)) and this can be done in n log p steps using repeated squarings. The second test needs log n tests of the form gcd(f(X), X^{p^{m}} − X) = 1. Each such test uses the Euclidean algorithm that needs m operations with degree ≤ m polynomials. So the running time of each such Euclidean algorithms is roughly O(n^{3}), although it might be faster in practice.

3 Finding Roots (mod p)

Let p ≠ 2 be a prime number. Let f ∈ 𝔽_{p}[X] be a polynomial of degree m, and we may assume that 0 is not a root. We want to find a root of f in E = 𝔽_{p^{n}}. Let q = p^{n}. If (f(X), X^{q−1} − 1) = 1 then f clearly has no roots in E. Otherwise, let f_{0}(X) = gcd(f(X), X^{q−1} − 1), and all the roots of f in E will be roots of f_{0}. Write f_{0}(X) = (X − a_{1}) ⋯ (X − a_{k}). Whether all the roots are equal it is easy to check: simply compute all the derivatives of f and each should divide f. Assume that not all the roots are equal.

Lemma 3.1. Let u ≠ v ∈ E. The the number of w ∈ E such that one of the following two cases is satisfied is (q − 1)/2:

1. u + w is a root of X^{(q−1)/2} − 1 and v + w is a root of X^{(q−1)/2} + 1.

2. u + w is a root of X^{(q−1)/2} + 1 and v + w is a root of X^{(q−1)/2} − 1.

Proof. For such a w it is clear that (u + w)/(v + w) is a quadratic nonresidue mod q, of which there are (q − 1)/2. Moreover, for every quadratic nonresidue c there is a unique w such that (u + w)/(v + w) = c since u ≠ v.

For d ∈ E write f_{d}(X) = f_{0}(X − d). Then the roots of f_{d} are a_{1} + d, …, a_{k} + d and by the lemma above for half of the d’s, there exist i, j such that a_{i} ≠ a_{j} and d satisfies the conditions in the lemma.

Proposition 3.2. If d satisfies the conditions in the lemma for a_{i}, a_{j} then gcd(f_{d}(X), X^{(q−1)/2}− 1) = h_{d}(X) has degree < deg f_{d}(X).

Proof. Otherwise f_{d}(X) | X^{(q−1)/2} − 1 so all the roots are quadratic residues which contradicts the assumption on d.

Algorithm 3.3.

Input f.

Compute f_{0}(X) = gcd(f(X), X^{q−1} − 1).

Choose d ∈ E randomly.

Compute gcd(f_{d}(X), X^{(q−1)/2}−1) = h_{d}(X). With probability 1/2 we have deg h_{d}(X) < deg f_{d}(X). Repeat until this happens.

Then h_{d}(X) | f_{d}(X) so h_{d}(X + d) | f_{0}(X) is a proper factor.

Repeat the algorithm for h_{d}(X + d) until reach a linear factor.

Output a root of the last linear factor which will be a root of f(X) in E.

Problem 3.4. For a prime p ≡ 1 (mod 4) find a, b integers so that p = a^{2} + b^{2}.

Proof. Let u be a root of X^{2} + 1 (mod p), found as above. Then you know that (a+bi) | (u+i) so use the Euclidean algorithm in ℤ[i] to find a+bi = gcd(p, u+i).

4 Factorisation (mod p)

4.1 Theory

Let f ∈ 𝔽_{p}[X] be a polynomial of degree n. We would like to factor f into irreducible polynomials in 𝔽_{p}[X]. Test to see if irreducible, stop if yes. Otherwise continue.

For each k ∈ {1, …, n} find h_{k}(X) = gcd(f(X), X^{p^{k}−1} − 1). For each h_{k} ≠ 1 we have h_{k}(X)|f(X) and all the roots of h_{k}(X) are in 𝔽_{p^{k}}. Use the above algorithm to find an α ∈ 𝔽_{p^{k}} such that h_{k}(α) = 0. Find the minimal polynomial g_{α}(X) of α over 𝔽_{p}. Then clearly g_{α}(X) will be an irreducible factor of f(X).

Divide by g_{α}(X) and repeat.

Theorem 4.1. This works.

Proof. The only problem that may occur is that all the h_{k}(X) are 1. Since f(X) is reducible then f = f_{1}^{ℓ_{1}} ⋯ f_{r}^{ℓ_{r}}. Then the roots of f_{1} are in 𝔽_{p^{deg f_{1}}} so h_{deg f_{1}} ≠ 1.

4.2 Running Time

Let α be in 𝔽_{p^{k}} and in no smaller field (easy to check using powers of Frobenius). Then the minimal polynomial has degree k so simply find a relation between 1, α, …, α^{k} using simple linear algebra.