What is the fastest known way to check if a given polynomial of degree $n$ in $F_{2}[X]$ is primitive?

In response to Greg Kuperberg's answer. If we known factorization of $2^{n} - 1$, then what is the complexity?

  • $\begingroup$ Polynomial over what? $\endgroup$ – Igor Rivin Nov 16 '11 at 16:42
  • 4
    $\begingroup$ More context would help. There are at least two unrelated definitions of a primitive polynomial, and it’s not clear which one you have in mind: en.wikipedia.org/wiki/Primitive_polynomial . $\endgroup$ – Emil Jeřábek Nov 16 '11 at 16:42

You first check that its roots lie in $\mathbb{F}_{2^n}$ by computing $X^{2^n}$ mod the polynomial $p(X)$ and checking that you get $X$. Then you want to know that the roots don't lie in a subfield, i.e., that $p(X)$ is irreducible. So for each maximal divisor $d$ of $n$, compute $\text{gcd}(p(X),X^{2^d}-X)$ and check that you get 1. Then you want to know that a root of $p$ has maximal order. So for each maximal divisor $d$ of $2^n-1$, check that $X^d$ mod $p(X)$ is not 1. The hardest step is to find the maximal divisors of $2^n-1$, which requires the prime factorization of $2^n-1$. If you don't know that, then you are probably sunk.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.