A Fast Algorithm for Testing Irreducibility of Trinomials mod 2 (preliminary report) 1
Richard P. Brent, Samuli Larvala, Paul A. Zimmermann, Inria Lorraine, Jardin Botanique · 2000
The standard algorithm for testing reducibility of a trinomial of prime degree r over GF(2) requires 2r+O(1) bits of memory and Θ(r) bit-operations. We describe an algorithm which requires only 3r/2 + O(1) bits of memory and significantly fewer bit-operations than the standard algorithm. Using the algorithm, we have found 18 new irreducible trinomials of degree r in the range 100151 ≤ r ≤ 700057. If r is a Mersenne exponent (i.e. 2−1 is a Mersenne prime), then an irreducible trinomial is primitive. Primitive trinomials are of interest because they can be used to give pseudorandom number generators with period at least 2 − 1. We give examples of primitive trinomials for r = 756839, 859433, and 3021377. The three results for r = 756839 are new. The results for r = 859433 extend and correct some computations of Kumada et al. [Math. Comp. 69 (2000), 811–814]. The two results for r = 3021377 are primitive trinomials of the highest known degree. Copyright c ©2000, the authors. rpb199tr typeset using LTEX