# 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? Commented Aug 20, 2016 at 22:39
• @Silicomancer Polynomials over $GF(2)$ always have zero-one coefficients. Commented Aug 20, 2016 at 22:54
• Oh, I see. Let me read more about that. Totally forgot the notations :( Commented Aug 20, 2016 at 23:04
• @Silicomancer The repeated squaring algorithm is described on Wikipedia. Commented Aug 27, 2016 at 14:41
• @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. Commented Aug 27, 2016 at 23:50