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).

 
Source
< Prev   CONTENTS   Source   Next >