On The Cycle Structure Of The NFSR And The Construction Of The M-sequence

The non-singular feedback shift register(NFSR)is a widely studied class of registers used in communications and cryptographic algorithms.The cycle structure is a commonly expression for describing the state diagram of NFSRs,that is,how many circles can the NFSR generate and what is the cycle length of each circle?Relatively,the problem of the cycle number distribution on NFSRs is the counting problem of NFSRs with the certain number of circles.In the 80s of last century,scholars at home and abroad have solved the linear and specially appointed nonlinear cycle structure of NFSRs.At the same time,currently only the number of NFSRs with one circle can be determined,but there are few results on the cycle number distribution on the rest.Meanwhile,the M-sequence is a kind of NFSR sequences with maximal cycle length.Because of its good pseudo randomness and high linear complexity,it is widely used in the communication coding.At present,the main methods to construct M-sequences are"Merging of cycles"and Recursion,but so far there is no better algorithm to construct a large number of M-sequences quickly.Aiming at the problems on the study of the cycle structure of NFSRs and the construction of M-sequence,the concept of M-sequence state cycle is introduced,the conceptual relation graph based on the cycle number of NFSRs is put forward,the problem of the number of NFSRs with the certain number of circles is studied,and the problem of the cycle number distribution is partly solved in this paper.At the same time,the some construction methods of a class of M-sequences feedback functions with the polynomial representation,minor term representation and so on are given.The main innovative achievements are as follows.1.On the problem of the number of NFSRs with 2 circlesThis problem is reduced to the problem of solving positive integer solutions of two indeterminate equation.Accordingly,the relationship between its number and the number of the assignment point in M-sequences state cycle is given for the series n;Based on the number of the assorted assignment points and aliquot circles,the new structure property law of M-sequence state cycle structure is presented;Based on the m-sequence,a class of the cycle structure with 2circles of NFSRs is constructed;The relation wtith the cycle number of NFSRs and the number of minor terms,as well as its relationship with the weight distribution of the M-sequence feedback function are presented.2.On the problem of the number of NFSRs with Z(n)circlesOn the basis of the role of double-lines,which are in the adjacency graph of the pure circulating shift register(PCR),in merging and splitting of cycles,we give calculation formulas of the lower bound of the number of NFSRs with Z(n),Z(n)-1,Z(n)-2 circles.Meanwhile the formalization description of feedback functions with the minor term representation of the entire NFSRs with Z(n)circles is given,and the reasonable conjectures about the cycle number distribution property on NFSRs are presented.At the same time,the limiting condition of the cycle length of NFSRs with Z(n)circles and an optimization algorithm for the synthesis problem on NFSRs are given.3.On the construction of the M-sequence feedback functions with the polynomial representationOn the basis of the structural properties of the M-sequence feedback function constructed by the m-sequence,the method of fast construction of a class of M-sequence feedback functions is proposed by combining the function transformation and function derivative.Meanwhile,the polynomial representation,amount and weight property of this class of M-sequence feedback functions are considered.4.On the construction of the M-sequence feedback functions with the minor term representationA deterministic structure respecting the adjacency graph of the PCR with the prime order is presented,and a theoretical construction method for the all floor weight class of M-sequences is given.As a special case of this method,the lower bound of its number is calculated and its corresponding feedback function is given.In this paper,the linearization matrix of the M-sequence feedback function is also investigated.It is proved that the 2~n-order permutation of the linearization matrix of the M-sequence feedback function must be a 2~n-order cyclic permutation.Currently,the cycle structure of NFSRs and the construction of M-sequences are still a hotspot and difficult problem in the communication and cryptography.The results of this paper will help to solve the problem of the cycle number distribution on NFSRs thoroughly,enrich the theory of the construction of M-sequences,and provide ideas for a deeper understanding of NFSRs.