# Irreducible trinomials

Ifa polynomial /(x) inZ2[x] has an even number of non-zero terms, then/(1) = 0, whence (x + 1) is a factor of /(x). Hence, the smallest number of non-zero terms an irreducible polynomial of degree > 2 in Z2 [x] can have is three. An irreducible trinomial of degree m in Z2[x] must be of the form xm + xk + 1, where 1 < к < m — 1. Choosing an irreducible trinomial /(x) e Z2[x] of degree m to represent the elements of the finite field F2™ = Z2[x]/(/(x)) can lead to a faster implementation of the field arithmetic. The following facts are sometimes of use when searching for irreducible trinomials.

• 4.75 Fact Let m be a positive integer, and let к denote an integer in the interval [1, m - 1].
• (i) If the trinomial xm + хк + 1 is irreducible over Z2 then so is xm + xm~k + 1.
• (ii) If m = 0 (mod 8), there is no irreducible trinomial of degree m in Z2[x],
• (iii) Suppose that either m = 3 (mod 8) or m = 5 (mod 8). Then a necessary condition for xm + xk + 1 to be irreducible over Z2 is that either к or m - к must be of the form 2d for some positive divisor d of m.

Tables 4.6 and 4.7 list an irreducible trinomial of degree m over Z2 for each m < 1478 for which such a trinomial exists.

# Primitive polynomials

Primitive polynomials were introduced at the beginning of §4.5. Let f(x)Zp[x] be an irreducible polynomial of degree m. If the factorization of the integer pm -1 is known, then Fact 4.76 yields an efficient algorithm (Algorithm 4.77) for testing whether or not f(x) is a primitive polynomial. If the factorization of pm — 1 is unknown, there is no efficient algorithm known for performing this test.

4.76 Fact Let p be a prime and let the distinct prime factors of pm 1 be r, гг,... , rt. Then an irreducible polynomial f(x) e Zp[x] is primitive if and only if for each i, 1 < i < t:

• (That is, x is an element of order pm - 1 in the field Zp[x]/(f(x)).)
• 4.77 Algorithm Testing whether an irreducible polynomial is primitive

INPUT: a prime p, a positive integer m, the distinct prime factors ri, r2,... ,rt of pm - 1, and a monic irreducible polynomial /(x) of degree m in Zp[x],

OUTPUT: an answer to the question: “Is /(x) a primitive polynomial?”

• 1. For i from 1 to t do the folio whig:
• 1.1 Compute/(x) = x(pm ЛУГ* mod /(x) (using Algorithm 2.227).
• 1.2 If/(x) = 1 then retum(“not primitive”).
• 2. Retum(“primitive”).

There are precisely ф(рт - 1 )/m monic primitive polynomials of degree m in Zp[x] (Fact 2.230), where ф is the Euler phi function (Definition 2.100). Since the number of monic irreducible polynomials of degree m in Zp[x] is roughly pm/m (Fact 4.67(h)), it follows that the probability of a random monic irreducible polynomial of degree m in Zp[x]

 m к m к m к m к m к m к m к 2 i 93 2 193 15 295 48 402 171 508 9 618 295 3 i 94 21 194 87 297 5 404 65 510 69 620 9 4 i 95 11 196 3 300 5 406 141 511 10 622 297 5 2 97 6 198 9 302 41 407 71 513 26 623 68 6 1 98 11 199 34 303 1 409 87 514 67 625 133 7 1 100 15 201 14 305 102 412 147 516 21 626 251 9 1 102 29 202 55 308 15 414 13 518 33 628 223 10 3 103 9 204 27 310 93 415 102 519 79 631 307 и 2 105 4 207 43 313 79 417 107 521 32 633 101 12 3 106 15 209 6 314 15 418 199 522 39 634 39 14 5 108 17 210 7 316 63 420 7 524 167 636 217 15 1 110 33 212 105 318 45 422 149 526 97 639 16 17 3 111 10 214 73 319 36 423 25 527 47 641 11 18 3 113 9 215 23 321 31 425 12 529 42 642 119 20 3 118 33 217 45 322 67 426 63 532 1 646 249 21 2 119 8 218 11 324 51 428 105 534 161 647 5 22 1 121 18 220 7 327 34 431 120 537 94 649 37 23 5 123 2 223 33 329 50 433 33 538 195 650 3 25 3 124 19 225 32 330 99 436 165 540 9 651 14 28 1 126 21 228 113 332 89 438 65 543 16 652 93 29 2 127 1 231 26 333 2 439 49 545 122 654 33 30 1 129 5 233 74 337 55 441 7 550 193 655 88 31 3 130 3 234 31 340 45 444 81 551 135 657 38 33 10 132 17 236 5 342 125 446 105 553 39 658 55 34 7 134 57 238 73 343 75 447 73 556 153 660 11 35 2 135 11 239 36 345 22 449 134 558 73 662 21 36 9 137 21 241 70 346 63 450 47 559 34 663 107 39 4 140 15 242 95 348 103 455 38 561 71 665 33 41 3 142 21 244 111 350 53 457 16 564 163 668 147 42 7 145 52 247 82 351 34 458 203 566 153 670 153 44 5 146 71 249 35 353 69 460 19 567 28 671 15 46 1 147 14 250 103 354 99 462 73 569 77 673 28 47 5 148 27 252 15 358 57 463 93 570 67 676 31 49 9 150 53 253 46 359 68 465 31 574 13 679 66 52 3 151 3 255 52 362 63 468 27 575 146 682 171 54 9 153 1 257 12 364 9 470 9 577 25 684 209 55 7 154 15 258 71 366 29 471 1 580 237 686 197 57 4 155 62 260 15 367 21 473 200 582 85 687 13 58 19 156 9 263 93 369 91 474 191 583 130 689 14 60 1 159 31 265 42 370 139 476 9 585 88 690 79 62 29 161 18 266 47 372 111 478 121 588 35 692 299 63 1 162 27 268 25 375 16 479 104 590 93 694 169 65 18 166 37 270 53 377 41 481 138 593 86 695 177 66 3 167 6 271 58 378 43 484 105 594 19 697 267 68 9 169 34 273 23 380 47 486 81 596 273 698 215 71 6 170 11 274 67 382 81 487 94 599 30 700 75 73 25 172 1 276 63 383 90 489 83 601 201 702 37 74 35 174 13 278 5 385 6 490 219 602 215 705 17 76 21 175 6 279 5 386 83 492 7 604 105 708 15 79 9 177 8 281 93 388 159 494 17 606 165 711 92 81 4 178 31 282 35 390 9 495 76 607 105 713 41 84 5 180 3 284 53 391 28 497 78 609 31 714 23 86 21 182 81 286 69 393 7 498 155 610 127 716 183 87 13 183 56 287 71 394 135 500 27 612 81 718 165 89 38 185 24 289 21 396 25 503 3 614 45 719 150 90 27 186 11 292 37 399 26 505 156 615 211 721 9 92 21 191 9 294 33 401 152 506 23 617 200 722 231

Table 4.6: Irreducible trinomials xm + xk + 1 over Z2. For each m, 1 < m < 722, for which an irreducible trinomial of degree m in Z2 [ж] exists, the table lists the smallest к for which xm + xk +1 is irreducible over Z2.

 m к m к m к m к m к m к m к 724 207 831 49 937 217 1050 159 1159 66 1265 119 1374 609 726 5 833 149 938 207 1052 291 1161 365 1266 7 1375 52 727 180 834 15 942 45 1054 105 1164 19 1268 345 1377 100 729 58 838 61 943 24 1055 24 1166 189 1270 333 1380 183 730 147 839 54 945 77 1057 198 1167 133 1271 17 1383 130 732 343 841 144 948 189 1058 27 1169 114 1273 168 1385 12 735 44 842 47 951 260 1060 439 1170 27 1276 217 1386 219 737 5 844 105 953 168 1062 49 1174 133 1278 189 1388 11 738 347 845 2 954 131 1063 168 1175 476 1279 216 1390 129 740 135 846 105 956 305 1065 463 1177 16 1281 229 1391 3 742 85 847 136 959 143 1071 7 1178 375 1282 231 1393 300 743 90 849 253 961 18 1078 361 1180 25 1284 223 1396 97 745 258 850 111 964 103 1079 230 1182 77 1286 153 1398 601 746 351 852 159 966 201 1081 24 1183 87 1287 470 1399 55 748 19 855 29 967 36 1082 407 1185 134 1289 99 1401 92 750 309 857 119 969 31 1084 189 1186 171 1294 201 1402 127 751 18 858 207 972 7 1085 62 1188 75 1295 38 1404 81 753 158 860 35 975 19 1086 189 1190 233 1297 198 1407 47 754 19 861 14 977 15 1087 112 1191 196 1298 399 1409 194 756 45 862 349 979 178 1089 91 1193 173 1300 75 1410 383 758 233 865 1 982 177 1090 79 1196 281 1302 77 1412 125 759 98 866 75 983 230 1092 23 1198 405 1305 326 1414 429 761 3 868 145 985 222 1094 57 1199 114 1306 39 1415 282 762 83 870 301 986 3 1095 139 1201 171 1308 495 1417 342 767 168 871 378 988 121 1097 14 1202 287 1310 333 1420 33 769 120 873 352 990 161 1098 83 1204 43 1311 476 1422 49 772 7 876 149 991 39 1100 35 1206 513 1313 164 1423 15 774 185 879 11 993 62 1102 117 1207 273 1314 19 1425 28 775 93 881 78 994 223 1103 65 1209 118 1319 129 1426 103 777 29 882 99 996 65 1105 21 1210 243 1321 52 1428 27 778 375 884 173 998 101 1106 195 1212 203 1324 337 1430 33 780 13 887 147 999 59 1108 327 1214 257 1326 397 1431 17 782 329 889 127 1001 17 1110 417 1215 302 1327 277 1433 387 783 68 890 183 1007 75 1111 13 1217 393 1329 73 1434 363 785 92 892 31 1009 55 1113 107 1218 91 1332 95 1436 83 791 30 894 173 1010 99 1116 59 1220 413 1334 617 1438 357 793 253 895 12 1012 115 1119 283 1223 255 1335 392 1441 322 794 143 897 113 1014 385 1121 62 1225 234 1337 75 1442 395 798 53 898 207 1015 186 1122 427 1226 167 1338 315 1444 595 799 25 900 1 1020 135 1126 105 1228 27 1340 125 1446 421 801 217 902 21 1022 317 1127 27 1230 433 1343 348 1447 195 804 75 903 35 1023 7 1129 103 1231 105 1345 553 1449 13 806 21 905 117 1025 294 1130 551 1233 151 1348 553 1452 315 807 7 906 123 1026 35 1134 129 1234 427 1350 237 1454 297 809 15 908 143 1028 119 1135 9 1236 49 1351 39 1455 52 810 159 911 204 1029 98 1137 277 1238 153 1353 371 1457 314 812 29 913 91 1030 93 1138 31 1239 4 1354 255 1458 243 814 21 916 183 1031 68 1140 141 1241 54 1356 131 1460 185 815 333 918 77 1033 108 1142 357 1242 203 1358 117 1463 575 817 52 919 36 1034 75 1145 227 1246 25 1359 98 1465 39 818 119 921 221 1036 411 1146 131 1247 14 1361 56 1466 311 820 123 924 31 1039 21 1148 23 1249 187 1362 655 1468 181 822 17 926 365 1041 412 1151 90 1252 97 1364 239 1470 49 823 9 927 403 1042 439 1153 241 1255 589 1366 1 1471 25 825 38 930 31 1044 41 1154 75 1257 289 1367 134 1473 77 826 255 932 177 1047 10 1156 307 1260 21 1369 88 1476 21 828 189 935 417 1049 141 1158 245 1263 77 1372 181 1478 69

Table 4.7: Irreducible trinomials xm+xk+1 over Z2. Foreachm, 723 1478, for which an irreducible trinomial of degree m in Z? [ж] exists, the table gives the smallest к for which xm + xk +1 is irreducible over Z-i.

being primitive is approximately ф(рт - l)/pm. Using the lower bound for the Euler phi function (Fact 2.102), this probability can be seen to be at least 1/(6 lnlnpm). This suggests the following algorithm for generating primitive polynomials.

4.78 Algorithm Generating a random monic primitive polynomial over Zp

INPUT: a prime p, integer m > 1, and the distinct prime factors ri,r2,... , rt of pm 1. OUTPUT: a monic primitive polynomial f(x) of degree m in Zp[x],

• 1. Repeat the following:
• 1.1 Use Algorithm 4.70 to generate a random monic irreducible polynomial f(x) of degree m in Zp[x].
• 1.2 Use Algorithm 4.77 to test whether f(x) is primitive.

Until f(x) is primitive.

2. Retum(/(x)).

For each to, 1 < m < 229, Table 4.8 lists a polynomial of degree m that is primitive over Z2. If there exists a primitive trinomial f(x) = xm + xk + 1, then the trinomial with the smallest к is listed. If no primitive trinomial exists, then a primitive pentanomial of the form f(x) = xm + xkl + xkl + xk:i + 1 is listed.

If p'" — 1 is prime, then Fact 4.76 implies that every irreducible polynomial of degree to in Zp[x is also primitive. Table 4.9 gives either a primitive trinomial or a primitive pentanomial of degree m over Z2 where to is an exponent of one of the first 27 Mersenne prunes (Definition 4.35).