A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

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

Authors:	Richard P Brent Samuli Larvala Paul Zimmermann

Affiliation:	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 $\operatorname{GF}(2)$ 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.

Keywords:	Irreducible polynomials irreducible trinomials primitive polynomials primitive trinomials Mersenne exponents Mersenne numbers random number generators

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载全文