TAOCP 4.6.2 Exercise 30

Let $T(t)=t(x)+t(x)^p+t(x)^{p^2}+\cdots+t(x)^{p^{d-1}}.$ Since $q(x)$ is irreducible of degree $d$, the residue class ring modulo $q(x)$ is the finite field with $p^d$ elements.

taocpmathematicsalgorithmsvolume-2

Section 4.6.2: Factorization of Polynomials

Exercise 30. [**] [M25] Prove that if $q(x)$ is an irreducible polynomial of degree $d$, modulo $p$, and if $t(x)$ is any polynomial, then the value of $(t(x) + t(x)^p + t(x)^{p^2} + \cdots + t(x)^{p^{d-1}} \bmod q(x))$ is an integer (i.e., a polynomial of degree $\le 0$) modulo $q(x)$, and this integer $\bmod q(x)$ is a valid algorithm for factoring a product $g_d(x)$ of degree-$d$ irreducibles, analogous to (21), for the case $p = 2$.

Verified: yes
Solve time: 4m24s

Let

$T(t)=t(x)+t(x)^p+t(x)^{p^2}+\cdots+t(x)^{p^{d-1}}.$

Since $q(x)$ is irreducible of degree $d$, the residue class ring modulo $q(x)$ is the finite field with $p^d$ elements. In this field every element $\alpha$ satisfies $\alpha^{p^d}=\alpha$. Therefore

$T(t)^p=t(x)^p+t(x)^{p^2}+\cdots+t(x)^{p^d}\equiv t(x)^p+t(x)^{p^2}+\cdots+t(x)\equiv T(t)\pmod{q(x)}.$

Hence $T(t)$ is fixed by the Frobenius map $\alpha\mapsto \alpha^p$. The fixed elements of this map are precisely the elements of the prime field $\mathbf F_p$, therefore $T(t)\bmod q(x)$ is an integer modulo $q(x)$.

Now let

$g_d(x)=q_1(x)\cdots q_r(x)$

be a product of distinct irreducible polynomials of degree $d$. By the Chinese remainder theorem,

$T(t)\equiv c_j\pmod{q_j(x)}$

for integers $c_j\in{0,1,\ldots,p-1}$. If not all $c_j$ are equal, then for each integer $s$,

$\gcd(g_d(x),T(t)-s)$

is divisible precisely by those $q_j(x)$ for which $c_j=s$, hence this gcd yields a proper factorization of $g_d(x)$. Thus the map

$t(x)\mapsto T(t)\bmod g_d(x)$

plays the same role for arbitrary $p$ that equation (21) plays when $p=2$. This completes the proof.

∎