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?
Asked
Active
Viewed 251 times
1
-
Polynomial over what? – Igor Rivin Nov 16 '11 at 16:42
-
4More 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: http://en.wikipedia.org/wiki/Primitive_polynomial . – Emil Jeřábek Nov 16 '11 at 16:42
1 Answers
3
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.
Greg Kuperberg
- 56,146