[Information Index] [Generation Index] [COS homepage]

Information on Primitive and Irreducible Polynomials

For now, COS only generates polynomials over GF(2), GF(3), GF(4) and GF(5).

For GF(2), the coefficients are either 0 or 1 and the rules for multiplication and addition are 0 = 0+0 = 1+1 = 0*0 = 0*1 = 1*0 and 1 = 0+1 = 1+0 = 1*1.

A polynomial over GF(2) is irreducible if it cannot be factored into non-trivial polynomials. For example, x2+x+1 is irreducible, but x2+1 is not, since x2+1 = (x+1)(x+1).

The order of a polynomial f(x) for which f(0) is not 0 is the smallest integer e for which f(x) divides xe+1. A polynomial over GF(2) is primitive if it has order 2n-1. For example, x2+x+1 has order 3 = 22-1 since (x2+x+1)(x+1) = x3+1. Thus x2+x+1 is primitive.

The number of degree n irreducible polynomials over GF(q) is

Lq(n)   =  
1
n
 
__
\
/   
d | n
µ(n/d) q d ,
where µ(m) is the Möbius function: 0 if m is not the product of distinct primes, +1 if it is the product of an even number of distinct primes, and -1 otherwise. For example, L2(6) = (26 - 23 - 22 + 2)/6 = 54/6 = 9 counts irreducible polynomials of degree 6 over GF(2). The number Lq(n) also counts the number of aperiodic necklaces of length n over the alphabet 0,1,...,q-1.

The number, Lq(n), of irreducible polynomials over GF(2) for n=1,2,...,15 is 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182. This is sequence A001037(M0116) in Neil J. Sloane's database of integer sequences.

The number of degree n primitive polynomials over GF(q) is Ø(qn -1)/n, where Ø(m) is Euler's totient function, the number of numbers less than m and relatively prime to m. For example, Ø(63) = |{2,4,5,8,...,62}| = 36 and thus the number of primitive polynomials of degree 6 over GF(2) is 36/6 = 6.

The number of primitive polynomials over GF(2) for n=1,2,...,15 is 1, 1, 2, 2, 6, 6, 18, 16, 48, 60, 176, 144, 630, 756, 1800. This is sequence A011260(M0107) in Neil J. Sloane's database of integer sequences.

Below we show the output of COS for n=6 and irreducible polynomials. Primitive polynomials are output in blue. The meanings of the different output options should be obvious.

Output
String
Coefficients
Polynomials
1 0 0 0 0 1 1 6, 1, 0 x6 + x1 + 1
1 0 1 0 1 1 1 6, 4, 2, 1, 0 x6 + x4 + x2 + x1 + 1
1 1 0 0 1 1 1 6, 5, 2, 1, 0 x6 + x5 + x2 + x1 + 1
1 0 0 1 0 0 1 6, 3, 0 x6 + x3 + 1
1 1 0 1 1 0 1 6, 5, 3, 2, 0 x6 + x5 + x3 + x2 + 1
1 0 1 1 0 1 1 6, 4, 3, 1, 0 x6 + x4 + x3 + x1 + 1
1 1 1 0 1 0 1 6, 5, 4, 2, 0 x6 + x5 + x4 + x2 + 1
1 1 1 0 0 1 1 6, 5, 4, 1, 0 x6 + x5 + x4 + x1 + 1
1 1 0 0 0 0 1 6, 5, 0 x6 + x5 + 1

Using our program we have computed some tables that may be of interest. The density of a polynomial is the number of non-zero terms. The index of a polynomial is the sum of the exponents of the non-zero terms.

Links

References


Programs available:
[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Monday, 23-May-2011 13:10:02 PDT.
There have been 13566 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.