2
$\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$
3
$\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$
  • $\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$ – Silicomancer Aug 20 '16 at 22:39
  • $\begingroup$ @Silicomancer Polynomials over $GF(2)$ always have zero-one coefficients. $\endgroup$ – Yuval Filmus Aug 20 '16 at 22:54
  • $\begingroup$ Oh, I see. Let me read more about that. Totally forgot the notations :( $\endgroup$ – Silicomancer Aug 20 '16 at 23:04
  • $\begingroup$ 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? $\endgroup$ – Silicomancer Aug 21 '16 at 20:40
  • 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$ – Yuval Filmus Aug 27 '16 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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