Gao: Factoring Polynomials under GRH

We consider the following problem: Given a prime $p$ and $f \in \mathbb{F}_p[x]$, where $\deg f=n$, $f$ is separable, and $f$ splits completely, find a proper factor of $f$ (in deterministic polynomial time).

Berlekamp algorithm reduces general polynomials in $\mathbb{F}_q[x]$ ($q$ a power of $p$) to polynomials of the above type. Without GRH, we are stuck already at $x^2-a$. So throughout we assume GRH.

Ronyai (1988) shows that this can be done in time $(n^n \log p)^{O(1)}$, or more precisely $(n^r \log p)^{O(1)}$ whenever $r \mid n$, $r>1$, so in particular if $n$ is even $f$ can be split in deterministic polynomial time. Bach, von zur Gathen and Lenstra (2001) give an algorithm with polynomial time if $\phi_k(p)$ is smooth for some $k$ where $\phi_k(x)$ is the $k$th cyclotomic polynomial. Evdokimov (1994) shows for any $n$ and $p$, $f$ can be factored in time $(n^{\log n}\log p)^{O(1)}$. We discuss work in Cheng and Huang (2000), and Gao (2001) plus some unpublished results. GRH will be needed only to compute an $r$th nonresidue in $\mathbb{F}_p$ or in its extensions, for $1 \leq r \leq n$.

Definition. An algebra $R/\mathbb{F}_p$ is called elementary if $R \cong (\mathbb{F}_p)^{\bigoplus m}$ for some $m$.

Let $R$ be elementary over $\mathbb{F}_p$. Then we write $R=\mathbb{F}_p \epsilon_1 + \dots + \mathbb{F}_p \epsilon_m$ where the $\epsilon_i$ are primitive idempotents, which are unique in $R$.

Fact.

1. If $f,g \in R[x]$, then $\gcd(f,g)$ can be defined properly and can be computed in deterministic polynomial time for any elementary algebra $R$.

2. If $f \in R[x]$ is monic, separable (i.e. $(f,f')=(1)$), and $f$ splits completely, then $R_1=R[x]/(f(x))$ is also elementary. Given a zerodivisor in $R_1$, one can compute a proper factor of $f$ or a zerodivisor of $R$.

3. Given a nontrivial ring endomorphism of $R_1$ over $R$, one can find a proper factor of $f$ or a zerodivisor of $R$. (Need GRH to get an $r$th nonresidue, for $1 \leq r \leq n$, where $n=\deg f$.)

4. Given a quadratic nonresidue in $\mathbb{F}_p$, there is a deterministic polynomial time algorithm for computing square roots in $R$. More precisely we have a function $\sigma: R \to R$, such that (i) $\sigma(A)$ is a square root of $A$ if $A$ is a square in $R$, (ii) if $A=\sum_{i=1}^m a_i\epsilon_i \in R$, $a_i \in \mathbb{F}_p$, then
   $$\sigma(A)=\sum_{i=1}^{m} \sigma(a_i)\epsilon_i,$$
   and (iii) for $a \in \mathbb{F}_p$, $\sigma(a^2) = \pm a$. For example, if $p \equiv 3\pmod{4}$, then we can take $\sigma(A)=A^{(p+1)/4}$, and for $a \in \mathbb{F}_p$,
   $$\sigma(a^2)= \begin{cases} a, & \text{if $a$ is a square}, \\ -a, & \text{otherwise}. \end{cases}$$

Now let $f \in \mathbb{F}_p[x]$ be separable, so that

$$f=\prod_{i=1}^n (x-a_i), a_i \in \mathbb{F}_p.$$

To factor $f$, define

$$R_2=\mathbb{F}_p[z_1,z_2]/(f(z_1),f(z_2)),$$

which is the tensor product of $\mathbb{F}_p[z]/(f(z))$ with itself. Then $R_2$ is an elementary algebra. In the following, we will identity $z_1$ and $z_2$ with their images in $R_2$. Let

$$\epsilon_i=\frac{\prod_{j \neq i} (z_1-a_j)}{\prod_{j \neq i}(a_i-a_j)}, 1 \leq i \leq n,$$

and

$$\eta_i=\frac{\prod_{j \neq i} (z_2-a_j)}{\prod_{j \neq i}(a_i-a_j)}, 1 \leq i \leq n.$$

Then $\epsilon_i\eta_j$, $1 \leq i,j \leq n$, are all the primitive idempotents of $R_2$. They have the following properties:

$$\sum_{i=1}^{n} \epsilon_i=1, \sum_{j=1}^{n} \eta_j =1,$$

and

$$z_1 = a_1\epsilon_1+\dots+a_n\epsilon_n=\sum_{i,j}a_i\epsilon_i\eta_j,$$

$$z_2 = a_1\eta_1+\dots+a_n\eta_n=\sum_{i,j} a_j\epsilon_i\eta_j.$$

Let

$$A = \frac{1}{2}(z_1 + z_2 + \sigma( (z_1- z_2)^2) \in R_2,$$

which can be computed in deterministic polynomial time. Then

$$A=\sum_{i,j}\frac{1}{2}(a_i+a_j+\sigma((a_i-a_j)^2)\epsilon_i\eta_j$$

where

$$\frac{1}{2}(a_i+a_j+\sigma((a_i-a_j)^2))= \begin{cases} a_i,... ... \\ a_j, & \text{if }\sigma((a_i-a_j)^2)=a_j-a_i. \end{cases}$$

Hence $A$ encodes information about the "squareness" of the differences of the roots of $f$. By using characteristic polynomials and gcd technique, one can extract the factors of $f$.

Definition. For $1 \leq i \leq n$, define

$$\Delta_i=\{1\leq j \leq n:j \neq i, \sigma((a_i-a_j)^2)=-(a_i-a_j)\}.$$

Theorem. We can always find a proper factor of $f$ in $\mathbb{F}_p[x]$ except when

$$\char93 \Delta_i=(n-1)/2, 1 \leq i \leq n,$$ (1)

and in this exception case $f$ can be factored over $\mathbb{F}_p[z_1]$ as

$$f(x) = (x-z_1) f_0 f_1$$

where

$$f_0 = \sum_{i=1}^{n} \prod_{j \in \Delta_i} (x-a_j) \epsilon_i, \ f_1 = \sum_{i=1}^{n} \prod_{j \notin \Delta_i, j\neq i} (x-a_j) \epsilon_i.$$

To further factor $f_0$ over $R_1=\mathbb{F}_p[z_1]/(f(z_1))$, we compute in the ring

$$R_3 = R_1[z_2,z_3]/(f_0(z_2), f_0(z_3)),$$

and similarly for $f_1$. Theorem. We can always split $f_0$ or $f_1$ except when

$$\char93 (\Delta_i \cap \Delta_j)=(n-3)/4, 1 \leq i <j \leq n,$$ (2)

and in this exception case, $f_0$ is factored over $R_1[z_2]/(f_0(z_2))$ as

$$f_0(x)= (x-z_2) f_{00} f_{01}$$

where $f_{00}, f_{01} \in R_1[z_2][x]$ both of degree $(n-3)/4$; similarly over the ring $R_1[z_2]/(f_1(z_2))$,

$$f_1(x) = (x-z_2) f_{10} f_{11}.$$

A system of subsets satisfying () and () is called an Hadamard design. When $n \equiv 3 \bmod 4$ is a prime, there is always an Hadamard design.

To further split $f_{00}$, let $R_2= R_1[z_2]/(f_0(z_2))$, and we compute in the ring

$$R_4 = R_2[z_3,z_4]/(f_{00}(z_3), f_{00}(z_4)).$$

Similarly for $f_{01}$, $f_{10}$, and $f_{11}$. Theorem. We can always split $f_{00}$, $f_{01}$, $f_{10}$, or $f_{11}$ except when

$$\char93 (\Delta_i \cap \Delta_j \cap \Delta_k )=(n-7)/8, 1 \leq i < j < k \leq n.$$ (3)

It can be proved, however, that () is impossible. It remains open how to explore this information to obtain a proper factor of $f$ in $\mathbb{F}_p[x]$!

Back to the main index for Future directions in algorithmic number theory.