Study On Construction And Randomness Analysis Of Pseudorandom Sequences

Pseudorandom sequences have wide applications in simulation, software testing,global positioning systems, ranging systems, code division multiple-access systems, radarsystems, spread-spectrum communication systems, and stream ciphers. This dissertationinvestigate the construction and randomness analysis of pseudorandom sequences. Theauthor obtains main results as follows:(1) The linear complexity of modified Jacobi sequences and the corresponding minimalpolynomials are determined, the result proves the conjecture of Green theoreticallyat the same time. Hardware implementation of these sequences are also outlined.(2) A special type of polyphase Jacobi sequences is presented, the symbol distribution,linear complexity and minimal polynomials of these sequences are investigated.(3) Two kinds of generalized cyclotomic sequences of order four are introduced. Theautocorrelation values and linear complexity of these sequences are calculated. Thesequences are five-valued and three-valued sequences if the parameters are chosenproperly and they are quite good from the linear complexity viewpoint.(4) The linear complexity and minimal polynomials of new generalized cyclotomic se-quences of order two are determined. A scheme for hardware implementation isgiven. The results show the sequences also have high linear complexity.(5) The randomness results of the edited sequence for four special cases are investigatedand a new self editing generator is presented. The period, linear complexity andsymbol distribution of the self edited sequence are discussed in detail.(6) The [a,b]-self shrinking generator is presented, the construction allows users to gen-erate di?erent sequences using the same initial states and the same characteristicfeedback polynomials. The output sequences have exponential period, exponentiallinear complexity and good statistical properties. The stability analysis and theresults of local randomness tests are also given.(7) Fast algorithms for determining the k-error linear complexity profile of a sequenceover GF(2) and GF(q) with period p~n are proposed, where both 2 and q are primitiveroot modulo p~2.