As part of a problem to factorise $f = x^6 + x^3 + 1$ over $\mathbb F_{19}$, I've realised that $f$ is a factor of $x^{18} - 1 = (x^9 + 1)(x-1)(x^6 + x^3 + 1)(x^2 + x + 1)$ which splits into linear factors over this field. Hence $f$ must split into linear factors.
However in order to find those linear factors I'm trying to find roots of $x^9 + 1$ and then the left over roots will be the roots of $f$. Is there an easy way to find these roots short of calculating at every value of $\mathbb{F}_{19}$? Which I could have just done in the first place with $f$?
Thanks
Note that $x^9=-1$ and $x^{18}=1$. There are $8$ generators of $\mathbb{Z}_{18}\equiv\mathbb{Z}_9\times\mathbb{Z}_2\equiv\mathbb{F}_{19}^{\times}$. So these, along with $-1$ itself, are the nine roots to $x^9+1$. Find one generator of $\mathbb{F}_{19}^{\times}$, and then its odd powers will make up the nine roots. While there may be a deterministic way to find a generator, it may be quicker to check if $2$ is a generator. If not, then $-2\equiv 17$ will be (in this specific case, since $\mathbb{F}_{19}^{\times}\equiv\mathbb{Z}_9\times\mathbb{Z}_2$). $$\begin{align}2&\equiv2\\2^2&\equiv4\\2^3&\equiv8\\2^4&\equiv16\\2^5&\equiv13\\2^6&\equiv7\\2^7&\equiv14\\2^8&\equiv9\\2^9&\equiv18\end{align}$$ and we can see that $2$ has to be a generator. So the zeros are $$\begin{align}2&\equiv2\\2^3&\equiv8\\2^5&\equiv13\\2^7&\equiv14\\2^9&\equiv18\\2^{11}&\equiv15\\2^{13}&\equiv3\\2^{15}&\equiv12\\2^{17}&\equiv10\end{align}$$
$x^6+x^3+1=0$ can be solved with the quadratic formula, if you can take square roots and cube roots. $$\begin{align}x&=\sqrt[3]{\frac{-1\pm\sqrt{1-4}}{2}}\\&=\sqrt[3]{\frac{-1\pm\sqrt{16}}{2}}\\ &=\sqrt[3]{\frac{-1\pm4}{2}}\\ &=\sqrt[3]{{-10\pm40}}\\ &=\sqrt[3]{30}&&\text{or}&\sqrt[3]{-50}\\ &=\sqrt[3]{11}&&\text{or}&\sqrt[3]{7}\\ \end{align}$$
This actually shows us that $11$ and $7$ are the zeros to $x^2+x+1$. The only six values left to be zeros for $x^6+x^3+1$ are $4$, $5$, $6$, $9$, $16$, and $17$.
Alternatively, you can take the cube roots directly. We found $2$ is a generator, and from the first table we can see that $11=2^{12}=2^{30}=2^{48}$. So cube roots of $11$ are $2^{4}=16$, $2^{10}=17$, and $2^{16}=5$. Do similarly to get cube roots of $7$.