A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377

The standard algorithm for testing reducibility of a trinomial of prime degree r r over G F ( 2 ) GF(2) requires 2 r + O ( 1 ) 2r + O(1) bits of memory. We describe a new algorithm which requires only 3 r / 2 + O ( 1 ) 3r/2 + O(1) bits of memory and significantly fewer memory references and bit-operations than the standard algorithm. If 2 r − 1 2^r-1 is a Mersenne prime, then an irreducible trinomial of degree r r is necessarily primitive. We give primitive trinomials for the Mersenne exponents r = 756839 r = 756839 , 859433 859433 , and 3021377 3021377 . The results for r = 859433 r = 859433 extend and correct some computations of Kumada et al. The two results for r = 3021377 r = 3021377 are primitive trinomials of the highest known degree.