Finding Roots of Polynomials
Once a Hilbert polynomial \(H_D(x)\) has been computed, a root in \(\mathbb{F}_q\) must be found. It will be used as the \(j\)-invariant when constructing an elliptic curve. We discuss one method for finding roots of a polynomial in a given finite field below.
Squarefree Factorization
Usually the first step is to remove factors so that the polynomial is squarefree. This is unnecessary if we only want the roots because the method we use for extracting the degree 1 factors automatically removes repeated roots.
For completeness we describe how to make a polynomial squarefree in general.
In a field of characteristic 0, a squarefree version of \(f(x)\) can be obtained by computing \(f(x) / \mathrm{gcd}(f(x), f'(x))\).
In a field of characteristic \(p\) however, a polynomial \(f(x)\) satisfies \(f'(x) = 0\) precisely when \(f(x) = w(x)^p\) for some polynomial \(w(x)\).
Thus if it is known that the degree of \(H_D(x)\) is less than \(p\) we may use the same algorithm unchanged. Otherwise:
-
Compute \(f'(x)\).
-
If \(f'(x) = 0\), write \(f(x) = w(x)^p\), replace \(f\) with \(w\) and goto step 1, otherwise replace \(f(x)\) with \(f(x) / \mathrm{gcd}(f(x), f'(x))\) and goto step 1.
Distinct Degree Factorization
The next step is to factorize \(f(x)\) as
where each \(f_i\) is a product of irreducible polynomials of degree \(i\).
As we only care about the roots, we only need \(f_1(x)\). This is precisely \(\mathrm{gcd}(x^q - x, f(x))\) since \(x^q - x\) is the product of all irreducible polynomials of degree 1. Use repeated squaring to efficiently compute the latter polynomial.
In general, observe that if \(p(x)\) is an irreducible polynomial of degree \(d\) then \(\mathbb{F}_q [x] / p(x) \mathbb{F}_q [x]\) is a field of degree \(q^d\). Suppose we have \(x^{q^d} - x = p(x) q(x) + r(x)\). Since every element of the field has order \(q^d\), we see that \(r(x) = 0\). Hence \(p(x)\) is a factor of \(x^{q^d} - x\).
This suggests the following algorithm.
-
Compute \(f_1(x) = \mathrm{gcd}(x^q - x, f(x))\).
-
Compute \(f_2(x) = \mathrm{gcd}(x^{q^2} - x, f(x) / f_1(x))\).
-
Compute \(f_3(x) = \mathrm{gcd}(x^{q^3} - x, f(x) / f_1(x) / f_2(x))\).
…and so on until all factors are found.
The Cantor-Zassenhaus Algorithm
An algorithm of Cantor and Zassenhaus factorizes any polynomial whose irreducible factors have the same degree. We only need a special case. Suppose \(f(x)\) is a degree \(n\) polynomial that splits in our field.
-
Select a random polynomial \(r(x)\) of degree less than \(n\).
-
If \(\mathrm{gcd}(r(x), f(x))\ne 1\) then return the result.
-
Compute \(s(x)=r(x)^{(q-1)/2} mod f(x)\). Then \(\mathrm{gcd}(s(x)+1, f(x))\) is a proper factor with probability \(1-2^{n-1}\).
-
Repeat until successful.
For completeness we describe how to proceed with the general case. First assume \(q\) is odd. Then for any \(g(x) \in \mathbb{F}_q\), consider the polynomial:
Each element of \(\mathbb{F}_{q^d}\) is a root, so \(x^{q^d} - x\) divides this polynomial. Also, observe the right-hand side factors are mutually coprime. Since \(f\) is squarefree and is a product of irreducible degree \(d\) polynomials, using a fact from above gives:
This explains the above procedure.
When \(p = 2\), define \(u(x) = x + x^2 + ... + x^{2^{d-1}}\). Then for any \(g(x) \in \mathbb{F}_2[x]\) we have
thus \(f = \mathrm{gcd}(f, u \circ g) \mathrm{gcd}(f, u \circ g + 1)\) and we proceed as before.
Irreducible Polynomials
On a related note, a polynomial \(f(x) \in \mathbb{F}_q\) of degree \(n\) is irreducible if and only if
-
\(f(x) | x^{q^n} - x\)
-
For all primes \(d\) dividing \(n\),
\[ \mathrm{gcd}(f(x), x^{q^{n/d}} - x) = 1 \]