# Check if a given polynomial is primitive

I try to estimate error detection capabilities of arbitrary CRC polynomials. One important criteria is if a given polynomial is primitive. So I need an algorithm to check that. My goal is to write a C or C++ routine.

Unfortunately I only found analytical solutions for the problem on the web.

Is there some numerical algorithm for testing a given polynomial for primitivity?

Please consider that my mathematical knowledge wasted away during the last two decades. Any algorithm descriptions, pseudo code or code in a common programming language would be very helpful.

In order to check that a degree $n$ polynomial $P$ over $GF(2)$ is primitive, you first need to know the factorization of $2^n-1$ (you can look it up in tables, or use a CAS). Then, you test that $x^{2^n-1} \equiv 1 \pmod{P(x)}$ (using repeated squaring to do this efficiently), and that for every prime factor $p$ of $2^n-1$, $x^{(2^n-1)/p} \not\equiv 1 \pmod{P(x)}$.

You can also just use a CAS (computer algebra software). For example, using the free software Sage you can do

F.<x> = GF(2)[]
(x^8+x^6+x^5+x+1).is_primitive()


For more on the relevant mathematics, see the Wikipedia article.

• Do you know if there is a simplified algorithm considering that CRC polynomials are pretty simple, having only terms with coefficients that are either 0 or 1? – Silicomancer Aug 20 '16 at 22:39
• @Silicomancer Polynomials over $GF(2)$ always have zero-one coefficients. – Yuval Filmus Aug 20 '16 at 22:54
• Oh, I see. Let me read more about that. Totally forgot the notations :( – Silicomancer Aug 20 '16 at 23:04
• I am not sure if I understand the description correctly. x^(2^(n−1)) ≡ 1 (modP(x)) means I devide x^(2^(n−1)) by P(x), then I devide x^0 by P(x) using polynomial division. Than I take both remainders and check if they are equal. Is this correct? – Silicomancer Aug 21 '16 at 20:40
• @Silicomancer You just repeatedly square $x$ modulo $P(x)$, and then multiply things out (modulo $P(x)$) until you get $x^{2^n-1} \pmod{P(x)}$. If you want to know more, you are welcome to ask another question. – Yuval Filmus Aug 27 '16 at 23:50