Is there any fast way to check if the following equation holds?
$x^{2^q}-x$ mod $p(x)=0$
Polynomials are over finite field $GF(2^q)$
I am aware of the algorithm which uses repeated squaring. This algorithm can achieve a complexity of $O(log(2^q))$.
The above mentioned algorithm actually first calculates $x^{2^q}$ mod $p(x)$, and then compare it with $x$. However, since I only care about if $x^{2^q}=x$ mod $p(x)$. That is, I do not have to know what $x^{2^q}$ mod $p(x)$ is. I was thinking if there exists an algorithm that can solve this problem faster.
Thanks
You are trying to figure out if $p(x)$ divides $x^{2^q}-x$. This polynomial has precisely the elements of $\mathbb{F}_{2^{q}}$ as its roots, so $p(x)$ divides it if and only if $p(x)$ factors completely over your field, and has no repeated roots.
So one way is to find all roots of $p(x)$ in $\mathbb{F}_{2^{q}}$. This is obviously not the best way.
You could also use the Euclidean algorithm to check that the gcd of your two polynomials is $p(x)$. This might be fast, I'm not sure of the complexity.
I honestly think you probably do want to do the repeated squaring algorithm. This can be done pretty quickly, if you choose an appropriate representation for your field. This is a good reference: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.446.1991&rep=rep1&type=pdf though I think there is maybe a more recent one by Panario that may have better techniques.