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

    $\displaystyle \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$,

    \begin{displaymath}\sigma(a^2)=
\begin{cases}
a, & \text{if $a$ is a square}, \\
-a, & \text{otherwise}.
\end{cases} \end{displaymath}

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

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

To factor $ f$, define

$\displaystyle 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

$\displaystyle \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

$\displaystyle \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:

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

and

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

Let

$\displaystyle 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

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

where

\begin{displaymath}
\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} \end{displaymath}

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

$\displaystyle \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

$\displaystyle \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

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

where

$\displaystyle 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

$\displaystyle 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

$\displaystyle \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

$\displaystyle 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))$,

$\displaystyle 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

$\displaystyle 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

$\displaystyle \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.