Programming ECC

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.

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)/\gcd (f(x),f\prime (x))$.

In a field of characteristic $p$ however, a polynomial $f(x)$ satisfies $f\prime (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:

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 $\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 ${𝔽}_q[x]/p(x){𝔽}_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.

…and so on until all factors are found.

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.

For completeness we describe how to proceed with the general case. First assume $q$ is odd. Then for any $g(x)\in {𝔽}_q$, consider the polynomial:

Each element of ${𝔽}_{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 {𝔽}_2[x]$ we have

thus $f=\gcd (f,ucomposeg)\gcd (f,ucomposeg+1)$ and we proceed as before.

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