Partitioning the Period of a Class of m -Sequences and Application to Pseudorandom Number Generation
A. C. Arvillias, Dimitris G. Maritsas · Journal of the ACM · 1978
A criterion Is derived for the "q-equipartmon" of the period of m-sequences based on pnmmve trmomlals (PT's), 1 + D q + D" It is shown that the class of PT's with q = 2 t, where t is an integer, can be implemented efficiently so as to produce m parallel q phase-shifted versions of the same m-sequence with relative delays analytically evaluated.These implementations lead to the construction ofeffioent algontlmas for the generation of q-bit pseudorandom number sequences equivalent m correlation performance to the Tausworthe-type generators.The algonthrns are of the GFSR type introduced by Lewis and Payne.The advantage of utthzmg the specific class of PT's is that the mmahzauon procedure is not reqmred.The corresponding linear recurrences threctly yield coding for the generators which delwer q-bit number sequences uncorrelated over a length approximately equal to ( 2It is important that three members of this class, of degreesp = 127, 175, 521, respectively, are Merserm¢ prime KEY WORDS AND PHRASES' m-sequences, pseudorandom number generators, feedback shift registers, pmmtive polynomials, Tausworthe generators, Tootdl, Lewis and Payne, key generators, equipartition of m-sequences, GFSR, linear recurrences CR CATEGORIES 3.15, 5 5, 6.30, 8 1