Programming ECC - Finding Roots of Polynomials

Finding Roots of Polynomials

Once a Hilbert polynomial $H_{D} (x)$ has been computed, a root in $𝔽_{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, but 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) / \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 we proceed as follows. Write $f (x) = v (x) w (x)^{p}$ such that any factor of $v (x)$ appears less than $p$ times. TODO (See Ersin Karabudak's notes .)

Distinct Degree Factorization

In general, the next step is to factorize $f (x)$ as

f (x) = f_{1} (x) . . . f_{m} (x)

where each $f_{i}$ is a product of irreducible polynomials of degree $i$ . Then the Cantor-Zassenhaus algorithm is applied to each $f_{i}$ in turn to determine the individual factors.

As we only care about the roots, we only need $f_{1} (x)$ . This is precisely $\gcd (x^{q} - x, f (x))$ since $h (x) = x^{q} - x$ is the product of all irreducible polynomials of degree 1. By repeated squaring $h (x) mod f (x)$ can be computed efficiently.

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. (See Ersin Karabudak's notes .)

Select a random polynomial $r (x)$ of degree less than $n$ .
If $\gcd (r (x), f (x)) \neq 1$ then return the result.
Compute $s (x) = r (x)^{(q - 1) / 2} \mod f (x)$ . Then $\gcd (s (x) + 1, f (x))$ is a proper factor with probability $1 - 2^{n - 1}$ .
Repeat until successful.

Irreducible Polynomials

On a related note, a polynomial $f (x) \in 𝔽_{q}$ of degree $n$ is irreducible if and only if

$f (x) ∣ x^{q^{n}} - x$
For all primes $d$ dividing $n$ ,
$\gcd (f (x), x^{q^{d}} - x) = 1$