Factorize $x^4 + 4x^2 +1$ over $\mathbb{F}_{29}$

Question

How do I factorize $x^4 + 4x^2 +1$ over $\mathbb{F}_{29}$?

I checked that the discriminant $D = 16 -4 = 12$ is not a square ($12^{14} = -1 \mod 29$) so this polynomial has no roots. Therefore it's either irreducible or is a product of two polynomials of degree $2$.

In theory I can find all irreducible polynomials of degree $2$ but $29$ is too big to do it by hand so what do I do?

Answer 1

All operations below in this post are done in the field $\mathbb{F}_{29}$.

Write $x^4+4x^2+1 = (x^2+bx+c)(x^2-bx+d)$. [why can $x^4+4x^2+1$ be written this way]. Then doing out the multiplication yields

$$c-b^2+d=4$$ $$bc-bd = 0$$ $$cd = 1.$$

Now the equations $cd = 1$ and $c-b^2+d = 4$ together yields $b \not = 0$ [why is that] and thus the equation $c = d$. Thus plugging these into the above yields:

$$2c-b^2 = 4$$ $$c = d$$ $$c^2 = 1.$$

Now, one can check that $-2$ is not a square in $\mathbb{F}_{29}$ so the equation $2c-b^2 = 4$ has no integral solution where $c = 1$. However, for $c = d = -1$ the equation $-b^2 = 6$ has the solution $b = 9$. So to conclude, plugging in $b=9$ and $c=d=-1$:

$$x^4+4x^2+1 = (x^2+bx+c)(x^2-bx+d) = (x^2+9x-1)(x^2-9x-1).$$