首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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
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 $r$ over $\operatorname{GF}(2)$ requires $2r + O(1)$ bits of memory. We describe a new algorithm which requires only $3r/2 + O(1)$ bits of memory and significantly fewer memory references and bit-operations than the standard algorithm.

If $2^r-1$ is a Mersenne prime, then an irreducible trinomial of degree $r$ is necessarily primitive. We give primitive trinomials for the Mersenne exponents $r = 756839$, $859433$, and $3021377$. The results for $r = 859433$ extend and correct some computations of Kumada et al. The two results for $r = 3021377$ 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》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号