6
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.