TAOCP 4.6.2 Exercise 29

Let g(x)=p_1(x)p_2(x)\cdots p_r(x), where the $p_j(x)$ are distinct irreducible polynomials of degree $d$, and let $q=p^d$.

taocpmathematicsalgorithmsvolume-2

Section 4.6.2: Factorization of Polynomials

Exercise 29. [**] [M22] Let $g(x)$ be a product of two or more distinct irreducible polynomials of degree $d$, modulo an odd prime $p$. Prove that $\gcd(g(x), t(x)^{(p^d-1)/2} - 1)$ will be a proper factor of $g(x)$ with probability $\ge 1/2 - 1/(2p^d)$, for any fixed $g(x)$, when $t(x)$ is selected at random from among the $p^{nd}$ polynomials of degree $< 2d$ modulo $p$.

Verified: yes
Solve time: 2m38s

Let

$$ g(x)=p_1(x)p_2(x)\cdots p_r(x), $$

where the $p_j(x)$ are distinct irreducible polynomials of degree $d$, and let $q=p^d$. By the Chinese remainder theorem,

$$ \mathbf F_p[x]/(g)\cong \prod_{j=1}^r \mathbf F_q . $$

If $t(x)$ is chosen uniformly from the polynomials of degree $<rd=\deg g$, its residue class modulo $g$ is uniformly distributed in $\mathbf F_q^r$. Hence the residues

$$ a_j=t(x)\bmod p_j(x)\in\mathbf F_q $$

are independent and uniformly distributed.

In $\mathbf F_q$, where $q$ is odd, the polynomial

$$ y^{(q-1)/2}-1 $$

vanishes on exactly the $(q-1)/2$ nonzero quadratic residues and on no other elements. Therefore

$$ \gcd!\left(g(x),,t(x)^{(q-1)/2}-1\right) $$

contains $p_j(x)$ precisely when $a_j$ is a nonzero square. Since

$$ \Pr(a_j\text{ is a nonzero square})=\frac{q-1}{2q}, $$

the events for different $j$ are independent. The gcd fails to be a proper factor only in the two extreme cases: either every $a_j$ is a nonzero square, giving gcd $=g(x)$, or none is a nonzero square, giving gcd $=1$. Thus

$$ \Pr(\text{proper factor}) = 1-\left(\frac{q-1}{2q}\right)^r -\left(\frac{q+1}{2q}\right)^r . $$

Since $r\ge2$,

$$ \left(\frac{q-1}{2q}\right)^r + \left(\frac{q+1}{2q}\right)^r \le \left(\frac{q-1}{2q}\right)^2 + \left(\frac{q+1}{2q}\right)^2 = \frac{q^2+1}{2q^2}. $$

Therefore

$$ \Pr(\text{proper factor}) \ge 1-\frac{q^2+1}{2q^2} = \frac12-\frac1{2q^2} \ge \frac12-\frac1{2q}. $$

Substituting $q=p^d$ gives

$$ \Pr!\left( \gcd!\left(g(x),t(x)^{(p^d-1)/2}-1\right) \text{ is a proper factor of }g(x) \right) \ge \frac12-\frac1{2p^d}. $$

This completes the proof.

∎