Algorithms for finding almost irreducible and almost primitive trinomials
Richard P. Brent, Paul Zimmermann · 2004
Dedicated to Hugh Cowie Williams on the occasion of his 60th birthday. Abstract. Consider polynomials over GF(2). We describe ecient al- gorithms for finding trinomials with large irreducible (and possibly prim- itive) factors, and give examples of trinomials having a primitive factor of degree r for all Mersenne exponents r = ±3 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 k 12. These trinomials enable ecient representations of the finite field GF(2 r ). We show how trinomials with large primitive factors can be used eciently in applications where primitive trinomials would normally be used.