Institution: | Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX1 3QD, England ; Helsinki University of Technology, Espoo, Finland ; LORIA/INRIA Lorraine, 615 rue du jardin botanique, BP 101, F-54602 Villers-lès-Nancy, France |
Abstract: | The standard algorithm for testing reducibility of a trinomial of prime degree over requires bits of memory. We describe a new algorithm which requires only bits of memory and significantly fewer memory references and bit-operations than the standard algorithm. If is a Mersenne prime, then an irreducible trinomial of degree is necessarily primitive. We give primitive trinomials for the Mersenne exponents , , and . The results for extend and correct some computations of Kumada et al. The two results for are primitive trinomials of the highest known degree. |