rpb212 (original) (raw)
Algorithms for finding almost irreducible and almost primitive trinomials
212. R. P. Brent and P. Zimmermann, Algorithms for finding almost irreducible and almost primitive trinomials, in Primes and Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams(edited by A. van der Poorten and A. Stein),Fields Institute Communication FIC/41, The Fields Institute, Toronto, published by the American Mathematical Society, 2004, 91-102. Invited paper presented at a conference in Banff, Canada, May 2003.
Preprint: dvi (28K), pdf (242K), ps (84K).
Overhead Transparencies (for the Banff talk): dvi (14K), pdf (224K), ps (144K).
Abstract
Consider polynomials over 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 = +3 mod 8 for r the range (5, 107), 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 efficient representations of the finite fields GF(2_r_). We show how trinomials with large primitive factors can be used efficiently in applications where primitive trinomials would normally be used.
Comments
This paper extends the algorithm of [199] to "almost irreducible" and "almost primitive" trinomials. See [211] for an application to random number generators.
A related talk (presented at ECCAD03, Clemson) on _Primitive and Almost Primitive Trinomials over GF(2)_is available here.
See the online descriptionfor the current status of the search for almost primitive trinomials.