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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityWhat 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^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.