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.
3
-
1$\begingroup$ Not always! $x^5+x+1 = (x^2+x+1)(x^3+x^2+1)$ $\endgroup$– Will SawinCommented Jun 28, 2013 at 17:27
-
$\begingroup$ 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. $\endgroup$– Will SawinCommented Jun 28, 2013 at 17:30
-
$\begingroup$ 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). $\endgroup$– Dietrich BurdeCommented Jun 28, 2013 at 20:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
