RIMITIVE POLYNOMIALS The table in this appendix contains prime factorizations of numbers of the form 2nd - 1, and a listing of selected primitive polynomials of degree n over GF(2). For further information on factorization sof 2nd - 1, see Reisel [1] and Brilllhart et al. [9]. Useful tables of primitive polynomials have been pub- lished by Peterson and Weldon [2], Watson [3], Stahnke [4], Zierler and Brillhart [5, 6], Zierler [7], and Lidl and Niederreiter [8]. In certain listings the notation F(n) will be used to represent the factor- ization of 2n - 1. For example, since 240-1(220-1)(2201) the factorization of 240 - 1 reads F(20) X 17 X 61681, indicating that the factorization of 220 1 should be inserted. Clearly 17 X 61681 must be the factorization of 220 + 1. The primitive polynomials in this table all have a small number of nonzero terms, and therefore will be represented by the set In of intermediate pow- ers of Z present in the polynomial. For example, the primitive polynomial z24 is represented by P24 = (4,3,1), = i.e., n F(n) 3 x 5 (1), (3) 8 3 x 5 x 17 (4,3,2), (6,5,1) 7 x 73 3 x 11 x 31 23 x 89 (6,4,1), (7,4,3) (4,3,1) 3 x 43 x 127 (5,3,1), (12,11,1) 7 x 31 x 151 (1), (4), (7) 3 x 5 x 17 x 257 (5,3,2), (12,3,1) 131071 (3), (5), (6) 33 X 7 X 19 X 73 (7), (9), (5,2,1) 524287 (5,2,1), (6,5,1) 3x52 x 11 x 31 x 41 7 x 127 x 137 3 X 23 X 89 X 683 Appendix 5B. Factorizations of 2n - 1 and Selected Primitive Polynomials 23 47 x 178481 (5), (9) 32X5X7X 13 X 17 X 241 (7,2,1),(4,3,1) 25 31 x 601 x 1801 (3), (7) 3 X 2731 X 8191 (6,2,1), (8,7,1) 7 x 73 x 262657 (5,2,1), (8,7,1) 3x5X 29 X 43 X 113 X 127 (3), (9), (13) 29 233 X 1103 x 2089 30 32X7x11 x 31 x 151 x 331 (6,4,1), (16,15,1) 31 2147483647 (3), (6), (7), (13) 3X5X 17 X 257 X 65537 (22,2,1), (28, 27, 1) 7x 23 x 89 x 599479 (13), (6,4,1) 3x 43691 X 131071 (15, 14,1), (27,2,1) 31 x 71 X 127 X 122921 F(18)x5x 13 x 37 x 109 (11), ,(6,5,4,2,1) 37 223 X 616318177 (12,10,2), ( (6,4,1) 38 F(19) X 3 X 174763 (6,5,1) 39 7X 79 X 8191 X 121369 (4), (8), (14) 40 F(20) x 