World's most popular travel blog for travel bloggers.

[Answers] Check if a given polynomial is primitve

, , No Comments
Problem Detail: 

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.

Asked By : Silicomancer

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback