On The 2-adic Complexity Of Sequencens

Linear feedback shift registers(LFSR)and feedback with carry shift register(FCSR)are two kinds of pseudo-random sequence generators.The sequences generated by them have good pseudo-random properties such as long period,low autocorrelation and large linear complexity.They are widely used in CDMA communication system,global positioning system,ranging system,stream cipher and many other fields.In essence,any binary periodic sequence can be generated by LFSR or FCSR.The linear complexity based on LFSR and 2-adic complexity based on FCSR are important indexes to measure the pseudorandomness of periodic sequence.With the development of cryptography,a large numberof cryptographic attack methods have emerged.Generally speaking,LFSR sequences havesimilar "linear structure" and are difficult to effectively resist multiple attacks,but FCSR sequences have better pseudorandomness and stronger anti attack ability due to the introduction of several carry registers.It is a research hotspot in cryptography to constructpseudo-random sequences with FCSR and analyze the 2-adic complexity of sequences.This dissertation first introduces the knowledge of shift carry register,then summarizes the corresponding relationship between rational fraction and 2-adic number and rational approximation algorithm.Finally,by introducing some carry registers into FCSR,we realize the fast generation of 2-adic expansion sequence of rational fraction.With a new idea and method,we give the rational fraction representation of solving finite binary sequence We also use the linear algorithm of rational approximation to estimate the upperand lower bounds of 2-adic complexity of long binary sequences,and give some concreteexamplesThe feature set of DHM sequence,which has important application in CDMA communication system,is almost difference set.It is a kind of almost balanced binary sequence with optimal three-level autocorrelation and has good pseudo-random property.In thispaper,we construct a class of DHM sequences with a period of N=2q(where q?5(mod 8)is prime number)by using the fourth order cyclotomic class,and study andcalculate their 2-adic complexity from two different perspectives:one is to optimize theknown cryptography algorithm,and find the shortest FCSR to generate the DHM sequence by substituting a certain length of continuous subsegment into the known 2-adic algorithm,so as to obtain its 2-adic complex The other is to use the method proposed by Feng Keqin in the middle of 2019 to study and determine the 2-adic complexity of the DHM sequence by using the number theory tools such as "Gauss period","quadratic" Gauss sum"and the fourth-order cyclotomic number on the finite field.For some special cases(q=5),we use these two different methods to calculate the specific value of the2-adic complexity of the corresponding DHM sequence.The calculation results show that the 2-adic complexity of the periodic sequence is not less than half of its period,which shows that the sequence can resist the attack of the rational approximation algorithm.In addition,it is found that the result of 2-adic algorithm is smaller than the actual value.