Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
Polynomial over what? –  Igor Rivin Nov 16 '11 at 16:42
4  
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 . –  Emil Jeřábek Nov 16 '11 at 16:42
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.