MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Polynomial over what? – Igor Rivin Nov 16 '11 at 16:42
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: . – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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