UNB ECE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Irreducible Polynomials in GF(2)

Binary values expressed as polynomials can readily be manipulated using the rules of GF(2) arithmetic.

The table below shows all irreducible polynomials in GF(2) up to degree 8. (These do not correspond to the prime integers.)

Every irreducible polynomial P(x) of degree m is a factor of xn+1 for n = 2m-1. Smaller values of n may also work unless P(x) is also primitive. Primitive polynomials are shown highlighted in the table.

The LRS link shows the corresponding Linear Recursive Sequence. Only primitive polynomials give maximum length sequences.

Online Factoring Tool      Table of Factors      Factors of xn+1


INDEX BINARY IRREDUCIBLE P(x) Factor of xn+1   (smallest n) LRS
2 (10) x n=(none) [LRS]
3 (11) x+1 n=(all) [LRS]
7 (111) x2+x+1 n=3 [LRS]
11 (1011) x3+x+1 n=7  (primitive) [LRS]
13 (1101) x3+x2+1 n=7  (primitive) [LRS]
19 (10011) x4+x+1 n=15  (primitive) [LRS]
25 (11001) x4+x3+1 n=15  (primitive) [LRS]
31 (11111) x4+x3+x2+x+1 n=5,10,15 [LRS]
37 (100101) x5+x2+1 n=31  (primitive) [LRS]
41 (101001) x5+x3+1 n=31  (primitive) [LRS]
47 (101111) x5+x3+x2+x+1 n=31  (primitive) [LRS]
55 (110111) x5+x4+x2+x+1 n=31  (primitive) [LRS]
59 (111011) x5+x4+x3+x+1 n=31  (primitive) [LRS]
61 (111101) x5+x4+x3+x2+1 n=31  (primitive) [LRS]
67 (1000011) x6+x+1 n=63  (primitive) [LRS]
73 (1001001) x6+x3+1 n=9,18,27,36,45,54,63 [LRS]
87 (1010111) x6+x4+x2+x+1 n=21,42,63 [LRS]
91 (1011011) x6+x4+x3+x+1 n=63  (primitive) [LRS]
97 (1100001) x6+x5+1 n=63  (primitive) [LRS]
103 (1100111) x6+x5+x2+x+1 n=63  (primitive) [LRS]
109 (1101101) x6+x5+x3+x2+1 n=63  (primitive) [LRS]
115 (1110011) x6+x5+x4+x+1 n=63  (primitive) [LRS]
117 (1110101) x6+x5+x4+x2+1 n=21,42,63 [LRS]
131 (10000011) x7+x+1 n=127  (primitive) [LRS]
137 (10001001) x7+x3+1 n=127  (primitive) [LRS]
143 (10001111) x7+x3+x2+x+1 n=127  (primitive) [LRS]
145 (10010001) x7+x4+1 n=127  (primitive) [LRS]
157 (10011101) x7+x4+x3+x2+1 n=127  (primitive) [LRS]
167 (10100111) x7+x5+x2+x+1 n=127  (primitive) [LRS]
171 (10101011) x7+x5+x3+x+1 n=127  (primitive) [LRS]
185 (10111001) x7+x5+x4+x3+1 n=127  (primitive) [LRS]
191 (10111111) x7+x5+x4+x3+x2+x+1 n=127  (primitive) [LRS]
193 (11000001) x7+x6+1 n=127  (primitive) [LRS]
203 (11001011) x7+x6+x3+x+1 n=127  (primitive) [LRS]
211 (11010011) x7+x6+x4+x+1 n=127  (primitive) [LRS]
213 (11010101) x7+x6+x4+x2+1 n=127  (primitive) [LRS]
229 (11100101) x7+x6+x5+x2+1 n=127  (primitive) [LRS]
239 (11101111) x7+x6+x5+x3+x2+x+1 n=127  (primitive) [LRS]
241 (11110001) x7+x6+x5+x4+1 n=127  (primitive) [LRS]
247 (11110111) x7+x6+x5+x4+x2+x+1 n=127  (primitive) [LRS]
253 (11111101) x7+x6+x5+x4+x3+x2+1 n=127  (primitive) [LRS]
283 (100011011) x8+x4+x3+x+1 n=51,102,153,204,255 [LRS]
285 (100011101) x8+x4+x3+x2+1 n=255  (primitive) [LRS]
299 (100101011) x8+x5+x3+x+1 n=255  (primitive) [LRS]
301 (100101101) x8+x5+x3+x2+1 n=255  (primitive) [LRS]
313 (100111001) x8+x5+x4+x3+1 n=17,34,51,68,85,102,119,136,
153,170,187,204,221,238,255
[LRS]
319 (100111111) x8+x5+x4+x3+x2+x+1 n=85,170,255 [LRS]
333 (101001101) x8+x6+x3+x2+1 n=255  (primitive) [LRS]
351 (101011111) x8+x6+x4+x3+x2+x+1 n=255  (primitive) [LRS]
355 (101100011) x8+x6+x5+x+1 n=255  (primitive) [LRS]
357 (101100101) x8+x6+x5+x2+1 n=255  (primitive) [LRS]
361 (101101001) x8+x6+x5+x3+1 n=255  (primitive) [LRS]
369 (101110001) x8+x6+x5+x4+1 n=255  (primitive) [LRS]
375 (101110111) x8+x6+x5+x4+x2+x+1 n=85,170,255 [LRS]
379 (101111011) x8+x6+x5+x4+x3+x+1 n=85,170,255 [LRS]
391 (110000111) x8+x7+x2+x+1 n=255  (primitive) [LRS]
395 (110001011) x8+x7+x3+x+1 n=85,170,255 [LRS]
397 (110001101) x8+x7+x3+x2+1 n=255  (primitive) [LRS]
415 (110011111) x8+x7+x4+x3+x2+x+1 n=51,102,153,204,255 [LRS]
419 (110100011) x8+x7+x5+x+1 n=85,170,255 [LRS]
425 (110101001) x8+x7+x5+x3+1 n=255  (primitive) [LRS]
433 (110110001) x8+x7+x5+x4+1 n=51,102,153,204,255 [LRS]
445 (110111101) x8+x7+x5+x4+x3+x2+1 n=85,170,255 [LRS]
451 (111000011) x8+x7+x6+x+1 n=255  (primitive) [LRS]
463 (111001111) x8+x7+x6+x3+x2+x+1 n=255  (primitive) [LRS]
471 (111010111) x8+x7+x6+x4+x2+x+1 n=17,34,51,68,85,102,119,136,
153,170,187,204,221,238,255
[LRS]
477 (111011101) x8+x7+x6+x4+x3+x2+1 n=85,170,255 [LRS]
487 (111100111) x8+x7+x6+x5+x2+x+1 n=255  (primitive) [LRS]
499 (111110011) x8+x7+x6+x5+x4+x+1 n=51,102,153,204,255 [LRS]
501 (111110101) x8+x7+x6+x5+x4+x2+1 n=255  (primitive) [LRS]
505 (111111001) x8+x7+x6+x5+x4+x3+1 n=85,170,255 [LRS]

Fri May 17 22:22:47 ADT 2024
Last Updated: 26 JUL 2020
Richard Tervo [ tervo@unb.ca ] Back to the course homepage...