# Fast computation to check if $x^{2^q}-x$ mod $p(x)$ is 0

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 can certainly come up with some necessary conditions. In particular, we know that the image of $p(x)$ in $\mathbb Z_2[x]$ cannot have repeated factors, and can only have prime factors of degree dividing $q$. (assuming $p(x)$ has integer coefficients.) – Thomas Andrews Oct 6 '15 at 0:03
• @hardmath: I am sorry, I forgot to mention. Polynomials are over finite field $GF(2^q)$. Thanks for reminding. – Nan Oct 6 '15 at 0:16
• @Thomas: It is a good point. But I actually do not want to calculate root of $p(x)$. Actually, the condition check posted in this question is conducted to decide whether a root search is needed. If the equation posted in this question holds, then a root search will be conducted. Therefore, information about the roots are not available in advance. – Nan Oct 6 '15 at 0:22
• @Nan. I said nothing about roots. – Thomas Andrews Oct 6 '15 at 0:28
• @Thomas: I am sorry. I took a guess that image means the roots. I just started learning finite field. I tried to google image of a polynomial, yet did not find anything useful. Could you please kindly posted some link to that concept? Thank you for your patience. – Nan Oct 6 '15 at 0:33

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.

• Thank you for you reply. The reason I want to do the test on whether $p(x)$ divides $x^{2^q} - x$ is that I think this might be a faster way to tell how many distinct roots $p(x)$ has. That is, my ultimate goal is to find out the number of distinct roots. To clarify what I mentioned in my last comment. What I meant is that there might be some necessary conditions $p(x)$ has to satisfy to divide $x^{2^q} - x$. In that case, one does not have to actually compute the remainder. – Nan Oct 9 '15 at 15:16
• @Nan There are of course necessary conditions, but I'm not sure they are easy to check (for example, checking that you have no repeated roots might take enough work that it is not worth it). I'll update my answer with some other suggestions. – Morgan Rodgers Oct 9 '15 at 15:45
• @Nan: Checking for repeated roots is typically so easy that it should be done, unless you are certain for a priori reasons that none can exist. $p(x)$ has repeated roots if and only the GCD of $p(x)$ and $p'(x)$ is nontrivial (degree $\gt 0$). – hardmath Oct 15 '15 at 2:50
• @hardmath Of course, but if you are going to check that you may as well just check the GCD of $p(x)$ and $x^{2^{q}}-x$ instead. – Morgan Rodgers Oct 15 '15 at 5:27
• I'm guessing the degree of $p(x)$ may be much smaller than $2^q$. Checking the GCD of $p(x)$ and $x^{2^q} - x$ by the Euclidean algorithm would begin by dividing $p(x)$ into $x^{2^q} - x$, so if it were practical to do so, we would discover divisibility in the first step. – hardmath Oct 15 '15 at 11:20