# PETERSON'S TABLE OF IRREDUCIBLE POLYNOMIALS OVER GF(2)

This table was taken from Error-Correcting Codes by W. Wesley Peterson, MIT Press (1970), pages 251 -155. This table is to be used only by students of CMSC 442 for instructional purposes only.
```           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

...............................
```