# primitive polynomial in $F_2$

Let $d$ be a prime number. Is the polynomial $x^d+x+1$ a primitive polynomial? In other words I need the minimal polynomial of $\alpha$ in $F_{2^d}=F_{2}(\alpha)$.

Thank you.

-
Not always! $x^5+x+1 = (x^2+x+1)(x^3+x^2+1)$ – Will Sawin Jun 28 '13 at 17:27
If it is primitive for $d=p$, it will not be primitive for any $d\cong p$ modulo $2^p-1$, because then the polynomial will again be a multiple of $x^p+x+1$. The $d$ for which it is primitive are determined by a prime-like sieve, but they are not the primes. They are almost certainly less frequent than the primes. – Will Sawin Jun 28 '13 at 17:30
Such primitive polynomials yield binary Hamming codes. The number of monomials need not be 3 (but odd) in general, e.g., $x^8+x^4+x^3+x^2+1$ is primitive, too (but $x^8+x+1$ not). – Dietrich Burde Jun 28 '13 at 20:35

See http://oeis.org/A073639 for the list of n such that x^n+x+1 is primitive modulo 2. The sequence begins [2,3,4,6,7,15,22,60,63,127,153,471,532,865,900,1366] You will also find some pertinent references there.

I found this using Maple's function "Primitive(f(x)) mod p" which returns true if f(x) is primitive mod p, and false otherwise.

-