I'm trying to understand distinct-degree factorization from Wikipedia.
I'm trying the algorithm on paper with $q=9$ and $f(x) = (x+4)(x+5) = x^2+2 \in F_{q}$.
We start with $i=1$. I calculate $g = gcd(f, x^q-x) = gcd(f, 6x)$ but at this point I am not sure what to do since $6x$ is not a member of $F_{q}[x]$. I can't work out the gcd. Basically I'm finding that the algorithm breaks down.
Is this a limitation of the algorithm or am I doing something wrong?
In the field of $9$ elements, $x^2+2=x^2-1=(x+1)(x-1)$. The polynomial $x^9-x$ is zero at both $1$ and $-1$, so it is divisible by $x+1$ and by $x-1$. It follows that $\gcd(f,x^9-x)=f$. I don't know where you got $6x$.
I'm sure you're aware that the field of $9$ elements is not the ring of integers modulo $9$.