0
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ 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.) $\endgroup$
    – Thomas Andrews
    Oct 6, 2015 at 0:03
  • $\begingroup$ @hardmath: I am sorry, I forgot to mention. Polynomials are over finite field $GF(2^q)$. Thanks for reminding. $\endgroup$
    – Nan
    Oct 6, 2015 at 0:16
  • $\begingroup$ @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. $\endgroup$
    – Nan
    Oct 6, 2015 at 0:22
  • $\begingroup$ @Nan. I said nothing about roots. $\endgroup$
    – Thomas Andrews
    Oct 6, 2015 at 0:28
  • $\begingroup$ @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. $\endgroup$
    – Nan
    Oct 6, 2015 at 0:33

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Nan
    Oct 9, 2015 at 15:16
  • 1
    $\begingroup$ @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$). $\endgroup$
    – hardmath
    Oct 15, 2015 at 2:50
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    Oct 15, 2015 at 11:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .