From the following tables all irreducible polynomials of degree
16 or less over GF(2) can be found, and certain of their properties
and relations among them are given. A primitive polynomial with
a minimum number of nonzero coefficients and polynomials be-
longing to all possible exponents is given for each degree 17
through 34.
Polynomials are given in an octal representation. Each digit in
the table represents three binary digits according to the following
code:
0 0 0 0 2 0 1 0 4 1 0 0 6 1 1 0
1 0 0 1 3 0 1 1 5 1 0 1 7 1 1 1
The binary digits then are the coefficients of the polynomial, with
the high-order coefficients at the left. For example, 3525 is listed
as a loth-degree polynomial. The binary equivalent of 3525 is
0 1 1 1 0 1 0 1 0 1 0 1, and the corresponding polynomial is
X10 + X9 + X8 + X6 + X4 + X2 + 1.
The reciprocal polynomial of an irreducible polynomial is also
irreducible, and the reciprocal polynomial of a primitive poly-
nomial is primitive. Of any pair consisting of a polynomial and
its reciprocal polynomial, only one is listed in the table. Each
entry that is followed by a letter in the table is an irreducible
polynomial of the indicated degree. For degree 2 through 16,
these polynomials along with their reciprocal polynomials com-
prise all irreducible polynomials of that degree.
The letters following the octal representation give the following
information:
A, B, C, D Not primitive
E, F, G, H Primitive
A, B, E, F The roots are linearly dependent
C, D, G, H The roots are linearly independent
A, C, E, G The roots of the reciprocal polynomial are linearly
dependent
B, D, F, H The roots of the reciprocal polynomial are linearly
independent
The other numbers in the table tell the relation between the poly-
nomials. For each degree, a primitive polynomial with a minimum
number of nonzero coefficients was chosen, and this polynomial
is the first in the table of polynomials of this degree. Let a denote
one of its roots. Then the entry following j in the table is the
minimum polynomial of aj. The polynomials are included for
each j unless for some i < j either ai and aj are roots of the
same irreducible polynomial or ai and a-j are roots of the same
polynomial. The minimum polynomial of aj is included even if it
has smaller degree than is indicated for that section of the table;
such polynomials are not followed by a letter in the table.
Examples: The primitive polynomial (103), or X6 + X + 1 = p(X)
is the first entry in the table of 6th-degree irreducible polyno-
mials. If a designates a root of p(X), then a 3 is a root of
(127) and a5 is a root of (147). The minimum polynomial of
a9 is (015) = X3 + X2 + 1, and is of degree 3 rather than 6.
There is no entry corresponding to a17. The other roots of
the minimum polynomial of a17 are a34, a68 = a5, a10, a20,
and a40. Thus the minimum polynomial of a17 is the same as
the minimum polynomial of a5 , or (147). There is no entry
corresponding to a13. The other roots of the minimum poly-
nomial p13(X) of a13 are a26, a52, a104 = a41, a82 = a19 , and
a38 . None of these is listed. The roots of the reciprocal poly-
nomial P13*(X) of P13(X) are a-13 = a50, a-26 = a37, a-52 =
all, a-41 = a22, a-19 = a44 and a-38 = a25. The minimum poly-
nomial of all is listed as (155) or X6 + X5 + X3 + X2 + 1. The
minimum polynomial of a13 is the reciprocal polynomial of this,
or p13(X) = X6 + X4 + X3 + X + 1.
The exponent to which a polynomial belongs can be found as
follows: If a is a primitive element of GF(2m), then the order
e of aj is
e = (2m-1)/GCD(2m-1, j)
and e is also the exponent to which the minimum function of aj
belongs. Thus, for example, in GF(210), a55 has order 93, since
93 = 1023/GCD(1023, 55) = 1023/11
Thus the polynomial (3453) belongs to 93.
Marsh has published a table of all irreducible polynomials of
degree 19 or less over GF(2). In this table the polynomials are
arranged in lexicographical order; this is the most convenient
form for determining whether or not a given polynomial is ir-
reducible.
For degree 19 or less, the minimum-weight polynomials given
in this table were found in Marsh's tables. For degree 19 through
34, the minimum-weight polynomial was found by a trial-and-error
process in which each polynomial of weight 3, then 5, was tested.
The following procedure was used to test whether a polynomial
f(X) of degree m is primitive.
1. The residues of 1, X, X2, X4, ... , X2m-1 are formed
modulo f(X).
2. These are multiplied and reduced modulo f(X) to form the
residue of X2m-1. If the result is not 1, the polynomial is rejected.
If the result is 1, the test is continued.
3. For each factor r of 2m-1, the residue of Xr is formed by
multiplying together an appropriate combination of the residues
formed in Step 1. If none of these is 1, the polynomial is primitive.
Each other polynomial in the table was found by solving for the
dependence relations among its roots by the method illustrated at
the end of Section 8.1 in Peterson.
Table Factorization of 2m-1 into Primes
23 - 1 = 7 219 - 1 = 524287
24 - 1 = 3x5 220 - 1 = 3x5x5xl1x31x41
25 - 1 = 31 221 - 1 = 7X7X127x337
26 - 1 = 3x3x7 222 - 1 = 3x23x89x683
27 - 1 = 127 223 - 1 = 47x178481
28 - 1 = 3x5x17 224 - 1 = 3x3x5x7x13x17x241
29 - 1 = 7x73 225 - 1 = 31x601x1801
210 - 1 = 3x11x3 226 - 1 = 3x2731x8191
211 - 1 = 23x89 227 - 1 = 7x73x262657
212 - 1 = 3x3x5x7x13 228 - 1 = 3x5x29x43x113x127
213 - 1 = 8191 229 - 1 = 233x1103x2089
214 - 1 = 3x43x127 230 - 1 = 3x3x7x11x31x151x331
215 - 1 = 7x31x15 231 - 1 = 2147483647
216 - 1 = 3x5x17x257 232 - 1 = 3x5x17x257x65537
217 - 1 = 131071 233 - 1 = 7x23x89x599479
218 - 1 = 3x3x3x7xl9x73 234 - 1 = 3x43691x131071
DEGREE 2 1 7H
DEGREE 3 1 13F
DEGREE 4 1 23F 3 37D 5 07
DEGREE 5 1 45E 3 75G 5 67H
DEGREE 6 1 103F 3 1278 5 147H 7 111A 9 015
11 155E 21 007
DEGREE 7 1 211E 3 217E 5 235E 7 367H 9 277E
11 325G 13 203F 19 313H 21 345G
DEGREE 8 1 435E 3 567B 5 763D 7 551E 9 675C
11 747H 13 453F 15 727D 17 023 19 545E 21 613D
23 543F 25 433B 27 477B 37 537F 43 703H 45 471A
51 037 85 007
DEGREE 9 1 1021E 3 1131E 5 1461G 7 1231A 9 1423G
11 1055E 13 1167F 15 1541E 17 1333F 19 1605G 21 1027A
23 1751E 25 1743H 27 1617H 29 1553H 35 1401C 37 1157F
39 1715E 41 1563H 43 1713H 45 1175E 51 1725G 53 1225E
55 1275E 73 0013 75 1773G 77 1511C 83 1425G 85 1267E
DEGREE 10 1 2011E 3 2017B 5 2415E 7 3771G 9 2257B
11 2065A 13 2157F 15 2653B 17 3515G 19 2773F 21 3753D
23 2033F 25 2443F 27 3573D 29 2461E 31 3043D 33 0075C
35 3023H 37 3543F 39 21078 41 2745E 43 2431E 45 3061C
47 3177H 49 3525G 51 2547B 53 2617F 55 3453D 57 3121C
59 3471G 69 2701A 71 3323H 73 3507H 75 2437B 77 2413B
83 3623H 85 2707E 87 2311A 89 2327F 91 3265G 93 3777D
99 0067 101 2055E 103 3575G 105 3607C 107 3171G 109 2047F
147 2355A 149 3025G 155 2251A 165 0051 171 3315C 173 3337H
179 3211G 341 0007
DEGREE 11 1 4005E 3 4445E 5 4215E 7 4055E 9 6015G
11 7413H 13 4143F 15 4563F 17 4053F 19 5023F 21 5623F
23 4757B 25 4577F 27 6233H 29 6673H 31 7237H 33 7335G
35 4505E 37 5337F 39 5263F 41 5361E 43 5171E 45 6637H
47 7173H 49 5711E 51 5221E 53 6307H 55 6211G 57 5747F
59 4533F 61 4341E 67 6711G 69 6777D 71 7715G 73 6343H
75 6227H 77 6263H 79 5235E 81 7431G 83 6455G 85 5247F
87 5265E 89 5343B 91 4767F 93 5607F 99 4603F 101 6561G
103 7107H 105 704IG 107 4251E 109 5675E 111 4173F 113 4707F
115 7311C 117 5463F 119 5755E 137 6675G 139 7655G 141 5531E
147 7243H 149 762IG 151 7161G 153 4731E 155 4451E 157 6557H
163 7745G 165 7317H 167 5205E 169 4565E 171 6765G 173 7535G
179 4653F 181 5411E 183 5545E 185 7565G 199 6543H 201 5613F
203 6013H 205 7647H 211 6507H 213 6037H 215 7363H 217 7201G
219 7273H 293 7723H 299 4303B 301 5007F 307 7555G 309 4261E
331 6447H 333 5141E 339 7461G 341 5253F
DEGREE 12 1 10123F 3 12133B 5 10115A 7 121538 9 11765A
11 15647E 13 12513B 15 13077B 17 16533H 19 16047H 21 10065A
23 11015E 25 13377B 27 14405A 29 14127H 31 17673H 33 13311A
35 10377B 37 13565E 39 13321A 41 15341G 43 15053H 45 15173C
47 15621E 49 17703C 51 10355A 53 15321G 55 10201A 57 12331A
59 11417E 61 13505E 63 10761A 65 00141 67 13275E 69 16663C
71 11471E 73 16237E 75 16267D 77 15115C 79 12515E 81 17545C
83 12255E 85 11673B 87 17361A 89 11271E 91 10011A 93 14755C
95 17705A 97 1712IG 99 17323D 101 14227H 103 12117E 105 13617A
107 14135G 109 14711G Ill 15415C 113 13131E 115 13223A 117 16475C
119 14315C 121 16521E 123 13475A 133 114338 135 10571A 137 15437G
139 12067F 141 13571A 143 12111A 145 16535C 147 17657D 149 12147F
151 14717F 153 13517B 155 14241C 157 14675G 163 10663F 165 10621A
167 16115G 169 16547C 171 10213B 173 12247E 175 16757D 177 16017C
179 17675E 181 10151E 183 14111A 185 14037A 187 14613H 189 13535A
195 00165 197 11441E 199 10321E 201 14067D 203 13157B 205 14513D
207 10603A 209 11067F 211 14433F 213 16457D 215 10653B 217 13563B
219 116578 221 17513C 227 12753F 229 13431E 231 10167B 233 11313F
235 11411A 237 13737B 239 13425E 273 00023 275 14601C 277 16021G
279 16137D 281 17025G 283 15723F 285 17141A 291 15775A 293 11477F
295 11463B 297 17073C 299 16401C 301 12315A 307 14221E 309 11763B
311 12705E 313 14357F 315 17777D 325 00163 327 17233D 329 11637B
331 16407F 333 11703A 339 16003C 341 11561E 343 12673B 345 14537D
347 1771IG 349 13701E 355 10467B 357 15347C 359 11075E 361 16363F
363 11045A 365 11265A 371 14043D 397 12727F 403 14373D 405 13003B
407 17057G 409 10437F 411 10077B 421 14271G 423 14313D 425 14155C
427 10245A 429 11073B 435 10743B 437 12623F 439 12007F 441 15353D
455 00111 585 00013 587 14545G 589 1631IG 595 13413A 597 12265A
603 14411C 613 15413H 619 17147F 661 10605E 683 10737F 685 16355C
691 15701G 693 12345A 715 00133 717 16571C 819 00037 1365 00007
DEGREE 13 1 20033F 3 23261E 5 24623F 7 23517F 9 30741G
11 21643F 13 3017IG 15 21277F 17 27777F 19 35051G 21 34723H
23 34047H 25 32535G 27 31425G 29 37505G 31 36515G 33 26077F
35 35673H 37 20635E 39 33763H 41 25745E 43 36575G 45 26653F
47 21133F 49 22441E 51 30417H 53 32517H 55 37335G 57 25327F
59 23231E 61 25511E 63 26533F 65 33343H 67 33727H 69 27271E
71 25017F 73 26041E 75 21103F 77 27263F 79 24513F 81 32311G
83 31743H 85 24037F 87 30711G 89 32641G 91 24657F 93 32437H
95 20213F 97 25633F 99 31303H 101 22525E 103 34627H 105 25775E
107 21607F 109 25363F Ill 27217F 113 33741G 115 37611G 117 23077F
119 21263F 121 31011G 123 27051E 125 35477H 131 3415IG 133 27405E
135 34641G 137 32445G 139 36375G 141 22675E 143 36073H 145 35121G
147 3650IG 149 33057H 151 36403H 153 35567H 155 23167F 157 36217H
159 22233F 161 32333H 163 24703F 165 33163H 167 32757H 169 23761E
171 24031E 173 30025G 175 37145G 177 31327H 179 27221E 181 25577F
183 22203F 185 37437H 187 27537F 189 31035G 195 24763F 197 20245E
199 20503F 201 20761E 203 25555E 205 30357H 207 33037H 209 34401G
211 32715G 213 21447F 215 27421E 217 20363F 219 3350IG 221 20425E
223 32347H 225 20677F 227 22307F 229 33441G 231 33643H 233 24165E
235 27427F 237 24601E 239 36721G 241 34363H 243 21673F 245 32167H
247 21661E 265 33357H 267 26341E 269 31653H 271 37511G 273 23003F
275 22657F 277 25035E 279 23267F 281 34005G 283 34555G 285 24205E
291 26611E 293 3267IG 295 25245E 297 31407H 299 33471G 301 22613F
303 35645G 305 3237IG 307 34517H 309 26225E 311 35561G 313 25663F
315 24043F 317 30643H 323 20157F 325 37151G 327 24667F 329 33325G
331 32467H 333 30667H 335 22631E 337 26617F 339 20275E 341 36625G
343 20341E 345 37527H 347 31333H 349 31071G 355 23353F 357 26243F
359 21453F 361 36015G 363 36667H 365 34767H 367 34341G 369 34547H
371 35465G 373 24421E 375 23563F 377 36037H 391 31267H 393 27133F
395 30705G 397 30465G 399 35315G 401 3223IG 403 32207H 405 26101E
407 22567F 409 21755E 411 22455E 413 33705G 419 37621G 421 21405E
423 30117H 425 23021E 427 21525E 429 36465G 431 33013H 433 27531E
435 24675E 437 33133H 439 34261G 441 33405G 443 34655G 453 32173H
455 33455G 457 35165G 459 22705E 461 37123H 463 27111E 465 35455G
467 31457H 469 23055E 471 30777H 473 37653H 475 24325E 477 31251G
547 35163H 549 33433H 551 37243H 553 27515E 555 32137H 557 26743F
563 30277H 565 20627F 567 35057H 569 24315E 571 24727F 581 30331G
583 34273H 585 23207F 587 31113H 589 36023H 595 27373F 597 20737F
599 36235G 601 21575E 603 26215E 605 21211E 611 20311E 613 34003H
615 34027H 617 20065E 619 22051E 621 22127F 627 23621E 629 24465E
651 26457F 653 31201G 659 34035G 661 27227F 663 22561E 665 21615E
667 22013F 669 23365E 675 26213F 677 26775E 679 32635G 681 33631G
683 32743H 685 31767H 691 34413H 693 22037F 695 30651G 697 26565E
711 22141E 713 22471E 715 35271G 717 37445G 723 22717F 725 26505E
727 24411E 729 24575E 731 23707F 733 25173F 739 21367F 741 25161E
743 24147F 793 36307H 795 24417F 805 20237F 807 36771G 809 37327H
811 27735E 813 31223H 819 36373H 821 33121G 823 32751G 825 33523H
...............................