, (5.55) Memory-Efficient Linear Generators Table 5.5 Maximum periods N for twenty-stage binary LFSRs with characteristic polynomials of the form Q (z) over GF(2), where Q(z) has degree d. degree power period 1048575 where the leaving exponent I is the unique integer satisfying the relation (5.56) Assuming that the period of the sequence generated by Q(z) is maximal, i.e., is qd - 1 where d is the degree of Q(z), it is apparent that interleaving is not an efficient way to achieve sequences with long periods. As an exam- ple, the achievable periods for a register of twenty binary storage elements are tabulated in Table 5.5. 5.3.4 M-Sequences Linear-feedback shift registers with L stages which produce the maximum possible period q1 - 1 do in fact exist, and the sequences which they pro- duce are called maximal LFSR sequences or m-sequences. When the con- nection between shift register sequences over GF(q) and larger finite fields is established in Section 5.5, it will be apparent that irreducible polynomi- als of degree L over GF(q) generate sequences whose periods must be divi- sors of q1 - 1. Those special irreducible polynomials, which are the characteristic polynomials of m-sequences, are called primitive polynomials, and they exist for every degree over every finite field. Appendix 5B contains factorizations of 2L - 1 and a table of primitive polynomials over GF(2). Techniques described in Appendix 5A.8 can be applied to find other prim- itive/irreducible polynomials from those listed in Appendix 5B. It suffices at this point to note: THEOREM 5.3. A linear generator of a given memory size produces a sequence of elements from GF(q), with the largest possible period if and only if its characteristic polynomial is primitive over GF(q). Two sequences {bn} and {b'n}, each having period N, are called cyclically equivalent if there exists an integer T such that bn+T = b'n for all N. A pair Pseudonoise Generators Table 5.6 The number Np (L) of cyclically distinct m-sequences with linear span L. Np(L) Np(L) 27594 24000