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.

 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]

 Mon Mar 4 15:09:33 AST 2024 Last Updated: 26 JUL 2020 Richard Tervo [ tervo@unb.ca ]