Algorithms for Finding Almost Irreducible and Almost Primitive Trinomials

Abstract

Consider polynomials over $\mathrm{GF}(2)$. We describe efficient algorithms for finding trinomials with large irreducible (and possibly primitive) factors, and give examples of trinomials having a primitive factor of degree $r$ for all Mersenne exponents $r=\pm 3\mathrm{mod}8$ in the range $5<r<10^7$, although there is no irreducible trinomial of degree $r$. We also give trinomials with a primitive factor of degree $r=2^k$ for $3\le k\le 12$. These trinomials enable efficient representations of the finite field $\mathrm{GF}(2^r)$. We show how trinomials with large primitive factors can be used efficiently in applications where primitive trinomials would normally be used.

12 pages, 2 tables, preprint of paper for Hugh Williams 60th birthday conference

Cited by in corpus (1)

• Weber's class number problem and $p$-rationality in the cyclotomic $\hat{\mathbb{Z}}$-extension of $\mathbb{Q}$