What are prime and primitive polynomials? Please, I am not a mathematician so highly mathematical textbook language will not make sense, that is why I am forced to post this question here.
I am reading about Checksum and CRC data integrity techniques and I have come across the terms "primtive polynomial" and "prime polynomial". I will really appreciate if someone could give example of these and explain what makes them primitive and prime.
e.g about polynomials used in Cyclic Redundancy Check that are implemented using hardware feedback registers it says "The best ones are not necessarily prime (irreducible) nor primitive"
 A: A prime polynomial $f$ in $K[X]$ (where $K$ is a field, e.g. $k=\Bbb R$) is the same as an irreducible polynomial (because $K[X]$ is a UFD [= unique factorization domain]).
A polynomial $f$ is irreducible in $K[X]$ if the following holds : whenever you can write $f$ as a product $g \cdot h$, one of the two factors $g$ or $h$ is a non-zero constant.
For instance, $X^2+1$ is irreducible in $\Bbb R[X]$, but $x^4+4=(x^2-2 x+2) (x^2+2 x+2)$ is not.
Factorising polynomials can be difficult in general. Over finite fields, there are Berkelamp's algorithm and Cantor-Zassenhaus algorithm. A polynomial of degree $≤3$ is irreducible if and only if it has no roots.
Some examples: $x^2+x+1 \in \Bbb F_2[X]$ is irreducible, because you can't write it as $(x-a)(x-b)$ for some $a,b \in \Bbb F_2[X]$. On the other hand, $x^4+x^2+1 \in \Bbb F_2[X]$ is not irreducible, since you can factor it as $(x^2+x+1)^2 =x^4+2 x^3+3 x^2+2 x+1$ (recall that $2=0$ in $\Bbb F_2$).

Let $\Bbb F_{p^n} = \text{GF}(p^n)$ be the field with $p^n$ elements, which is an extension of the field $\Bbb F_p$.
You may know that its multiplicative group is a cyclic group, say generated by some element $a$ : we have $(\Bbb F_{p^n})^* = \langle a \rangle$, so that $\Bbb F_{p^n} = \Bbb F_p(a)$.
Then a primitive polynomial $f \in \Bbb F_p[X]$, in that context, is the minimal polynomial of $a$ over $\Bbb F_p$.
In particular, a primitive polynomial is irreducible. However, the converse doesn't hold: for instance, $x^4+x^3+x^2+x+1$ is irreducible in $\Bbb F_2$ but is not a primitive polynomial.
For examples about primitive polynomials, you can have a look at this question or this one.
