Para un polinomio $p(x)$ de grado $n$ con coeficientes en $GF(2)$ para ser primitivo, debe satisfacer la condición de que $2^n-1$ es el menor número entero positivo $e$ con la propiedad de que $$ x^e\equiv 1\pmod{p(x)}. $$ Has acertado.
Para que un polinomio sea primitivo, es necesario (pero no suficiente) que sea irreducible. Su polinomio "aleatorio" $$ x^4+x^2+x+1=(x+1)(x^3+x^2+1) $$ no pasa esta prueba de litio, así que no necesitamos comprobar nada más.
Siempre que implemento un campo finito de característica dos en un programa de ordenador, al principio genero una tabla de logaritmos discretos. Al hacerlo, también verifico automáticamente que $2^n-1$ es, de hecho, la menor potencia de $x$ que producen un remanente $=1$ . Para un in situ ejemplo ver la última mitad de mi respuesta a esta pregunta donde verifico que $x^3+x+1$ es primitivo mostrando que tenemos que subir a $x^7$ para obtener un resto igual a $1$ .
Hacerlo a mano se vuelve tedioso después de un tiempo. Hay varios atajos disponibles, si sabes que $p(x)$ es irreducible y si se conoce la factorización prima de $2^n-1$ . Estos dependen del hecho de que el grupo multiplicativo de $GF(2^n)$ es siempre cíclico. Su ejemplo de $p(x)=x^4+x^3+1$ es un ejemplo de ello. Es relativamente fácil decidir que es irreducible. Entonces la teoría de los grupos cíclicos dice que el más pequeño $e$ será el factor de $15$ . Por lo tanto, para demostrar que realmente es igual a quince basta con comprobar que ninguno de $e=1,3,5$ trabajo. Esto es fácil. La única comprobación no trivial es que $$ x^5\equiv x^5+x(x^4+x^3+1)=x^4+x\equiv x^4+x+(x^4+x^3+1)=x^3+x+1\not\equiv1\pmod{x^4+x^3+1}, $$ y esto nos da la prueba.
Incluso con los atajos, encontrar un polinomio primitivo de un grado determinado es una tarea que preferiría evitar. Así que utilizo tablas de búsqueda. Mi fuente favorita en línea está en
http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/primitive-polynomial-table.txt
Después de tener un polinomio primitivo, a menudo se quiere encontrar otros estrechamente relacionados. Por ejemplo, al calcular los polinomios generadores de un código BCH o un LFSR de una secuencia de Oro (u otra secuencia con estructura conocida) se encuentra la siguiente tarea. El polinomio primitivo dado es el llamado polinomio mínimo de cualquiera de sus raíces, digamos $\alpha$ . Estas construcciones requieren encontrar el polinomio mínimo de $\alpha^d$ para algunos $d$ . Por ejemplo $d=3$ o $d=5$ son muy comunes. El polinomio mínimo de $\alpha^d$ será primitivo, si $\gcd(d,2^n-1)=1$ y esto se cumple a menudo. Entonces, un álgebra relativamente básica de extensiones de campo te da un algoritmo para encontrar el polinomio mínimo deseado. Sin embargo, el espacio no me permite entrar en eso aquí.
