Could anyone suggest any good way to do it? (The only way I can think of is by looking for roots (There are none), checking a factorization into the product of a 6 and a 2 polynomial (Many unknowns for the coefficients), checking a factorization of a 5 and 3, and finally one of two 4 degrees. (And each check probably takes lot's of time, since it contains many variables)
Is there any smarter way to do it?
On
First one substitutes $z=x^4$ and arrives at $z^2-z+1=0$. Quadratic polynomials are easy to factor (over any field of characteristic $\neq 2$), here we get $(z-3)(z-5)$. Using a bit of Galois theory (see below) one can find $x^4-3=(x^2+2x+2)(x^2+5x+2)$ and $x^4-5=(x^2+x+4)(x^2+6x+4)$ and these polynomials of degree $2$ are irreducible.
The Galois group of the polynomial is generated by the Frobenius $\alpha \mapsto \alpha^7$, and it acts on the roots. This action is transitive iff the polynomial is irreducible. More precisely, every orbit gives rise to an irreducible factor. Let $\alpha \in \overline{\mathbb{F}_7}$ be a root of $x^4-3$. One checks directly that $\alpha \notin \mathbb{F}_7$, hence $\alpha \neq \alpha^7$. But $\alpha^{7^2}=\alpha \cdot (\alpha^4)^{12}=\alpha \cdot 3^{12}=\alpha$. Therefore, $(x-\alpha)(x-\alpha^7) \in \mathbb{F}_7[x]$ is an irreducible factor of $x^4-3$. The constant term is $\alpha^8=(\alpha^4)^2=3^2=2$. The linear coefficient is $\alpha+\alpha^7$, whose square is $\alpha^2+2 \alpha^8 + \alpha^{14}=\alpha^2 + 2 (\alpha^4)^2+\alpha^2 (\alpha^4)^3=\alpha^2+2 \cdot 2 + \alpha^2 \cdot 6=4$, hence $\alpha+\alpha^7 = \pm 2$. Thus, we find $x^4-3=(x^2+2x+2)(x^2+5x+2)$.
Of course this can also be verified by a direct computation, but using Galois theory (which is quite easy for finite fields) we can derive the irreducible factors. No brute force search or algorithm is necessary.
I will follow up on my comment here, because I have found a strategy.
EDIT: I screwed up in here somewhere and so have removed what I had written. Sorry to have now double-posted.