For the class of primitive trinomials xP+ xk+ 1 with (k, 2P-1) = 1, shift register constructions are presented which are designed to produce in parallel consecutive patterns, of k-consecutive bits each, of the corresponding m-sequence. The resultant class of register structures preserves the function of equivalent feedback shift registers (FSR's) with composite feedback logic while allowing a saving in the physical implementation which amounts to the complete elimination of modulo-2 adders. This accounts for the high-speed performance of the toggle-registers presented, and makes them suitable for a broad range of applications.

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

We propose a systematic way for analyzing split-up feedback shift register structures which generate parallel p-n sequences. The analysis aims towards determining the relative phase shifts among the various realizations of the same p-n sequence. The main design criterion is derived when such systems are used as pseudorandom number generators. The results of this analysis are incorporated in the procedure for constructing pseudorandom number sequences. A case study is presented to demonstrate the construction procedure and in the light of our analysis a critical assessment of a class of generators proposed by W. J. Hurd, is given. Two polynomials of degree n = 20 contained in the table reported by W. J. Hurd have been checked and proved to be nonprimitive. The purpose of this study is to ensure "safe" designs when pseudorandom number generating algorithms are constructed, based on high-degree recursions with many nonzero terms.