I would like to accelerate the search of prime factors of
$$2\uparrow \uparrow 4+3\uparrow \uparrow 4$$
In a question, I asked for a prime factor and another user also asked, whether this number is prime.
To accelerate the search, I want to use the fact that $-65536$ is a cubic residue for every prime factor $p$ and even a $9$-th-power-residue. That means, the congruence $x^3\equiv -65536\ (\ mod\ p\ )$ and even the congruence $x^9\equiv -65536\ (\ mod\ p\ )$ is solveable, if $p$ is a prime factor of the given number.
This should restrict the possible factors much more than the condition $(\frac{-3}{p})=1$ ($-3$ is a quadratic residue mod $p$), but I do not have any idea, how the restrictions look like.