6

Say I have a given polynomial $g(x)$ over the field $\mathbb Z_2 $. How can I find the minimal $n$ for which $g(x)|x^n-1$?

For example, I was told that for any $n<32768$, $g(x)=x^{15}+x^{14}+1$ does not divide $x^n-1$ (I have spotted that $2^{15}=32768$, however I don't know how to use this relation). How does one arrive at this conclusion?

Thanks.

SivanBH
  • 195
  • Here is a really useful paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.121.3592&rep=rep1&type=pdf – rtybase Apr 16 '17 at 11:35
  • @rtybase I see the relevance, in the sense that the polynomials dealt with are of the right form, but I don't see how to apply this to my problem. Could you elaborate please? – SivanBH Apr 16 '17 at 13:13
  • You need layman's explanation? – Takahiro Waki Apr 16 '17 at 16:23
  • Pretty much. This question came about as part of a homework assignment in a computer science course (dealing with CRC), rather than algebra. So I suppose the answer I'm looking for isn't this complicated. – SivanBH Apr 16 '17 at 16:41

2 Answers2

1

This is somewhat of a partial answer.

Suppose, as in your specific example, that $g(X)$ is coprime to $X$ and irreducible.

Let $t=deg(g)$. Since $g(X)$ is irreducible, adjoining any of its roots generates the unique field of degree $2^t$ over $\mathbb{F}_2$, i.e. $\mathbb{F}_{2^t}$. Since this is also known to be the set of roots of $X^{2^t}-X$, we have $g(X)|X^{2^t}-X$. Therefore it is always true that $g(X)|X^{2^{deg(g)}-1}-1$.

On the other hand, it is well known that $gcd(X^n-1,X^m-1)=X^{gcd(m,n)}-1$. Therefore the minimal polynomial of the form $X^n-1$ that $g$ divides has $n\mid2^{deg(g)}-1$.

In general, I don't think we can do any better than this: considering the roots of $g(X)$ as elements of the cyclic group $\mathbb{F}_{2^{deg(g)}}^{\times}$, they all have the same order, seeing as they are conjugates via Frobenius, and $2$ is prime to $\#\mathbb{F}_{2^{deg(g)}}^{\times}$. Therefore, for example, knowing whether this minimal $n$ is $2^{deg(g)}-1$ is like knowing whether the roots of $g(X)$ are generators of the multiplicative group. I don't know of a general way of answering this question without checking this explicitly for the polynomial.

So, in your example, $g(X)$ divides $X^{2^{15}-1}-1$, and to check it doesn't divide any lower power you only need to check that $X^{m}-1\neq 0 (\text{ mod } g(X))$ for $m\neq 2^{15}-1$ dividing $2^{15}-1$.

Gal Porat
  • 903
  • Thank you for the answer. Sadly I don't have the necessary mathematical knowledge to fully understand your explanation, and so it seems like this is out of the scope of what my lecturer had in mind. – SivanBH Apr 16 '17 at 15:50
0

This feels like it might be useful to think about the splitting field of $g(x)$ over $\mathbb{F}_2$.

By using some Galois theory, you can show that there exists only one field of order $q=p^k$ for some prime $p$ and positive integer $k$, up to isomorphism. Also, the non-zero elements of $\mathbb{F}_q$ form a multiplicative cyclic group. This means non-zero elements of $\mathbb{F}_q$ satisfy $X^{q-1}-1$.

This means if the splitting field of $g(X)$ is $\mathbb{F}_{q}$, then $g(x)$ divides $X^{q-1}-1$ over $\mathbb{F}_p$, as roots of $g(x)$ are in $\mathbb{F}_{q}$.

As for why $g(X)$ does not divide a lower power,I agree with Gal Porat is to check through the divisors of $2^{15}-1$. Although, just to reiterate you don't have to check $2^3-1$ or $2^5-1$ because if $g(X)$ did divide it, then the splitting field would be $\mathbb{F}_{2^5}$ and $\mathbb{F}_{2^3}$ instead of $\mathbb{F}_{2^{15}}$.

daruma
  • 2,469