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?
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? 


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^n1$, check that $X^d$ mod $p(X)$ is not 1. The hardest step is to find the maximal divisors of $2^n1$, which requires the prime factorization of $2^n1$. If you don't know that, then you are probably sunk. 

