Analysis On Construction And Randomness Of Pseudo-random Sequences

Pseudorandom sequences witness wide applications in simulation, software testing, global positioning systems, ranging systems, code division multiple-access systems, radar navigation systems, spread-spectrum communication systems, and stream ciphers. This dissertation investigates the construction and randomness analysis of a kind of binary cyclotomic sequences, four kinds of binary generalized cyclotomic sequences, and two kinds of nonbinary sequences. The author obtains main results as follows:(1). A new class of balanced sextic residue sequences is constructed, and it's corresponding randomness is analyzed. It's linear complexity and characteristic polynomial are determined by the factoring of polynomials theory and the trace function representation, respectively. The autocorrelation and k-error linear complexity of the sequences are investigated. Furthermore, a Maple program is designed to verify the validity of the autocorrelation.(2). Based on Whiteman's generalized cyclotomy, new binary generalized cyclotomic sequences of order 2^k and length pq are constructed. Their linear complexity and minimal polynomials are determined. It is shown that the minimum of linear complexity is (?) the maximum (q-1)p. By Berlekamp-Massey algorithm, these sequences have good linear complexity. When the values of p approach q, the sequences are approximately balanced.(3). Based on Ding and Helleseth's generalized cyclotomy, two classes of new generaized cyclotomic sequences of arbitrary order and length pq are constructed. One is balanced and the other have the imbalance q-p-1. Trace function representation and linear complexity of both sequences are determined. Results show that both the trace function representation and linear complexity are independent of their order, and only depend on the values of primes p and q. Thus we have resolved the linear complexity problem of these two classes of sequences utterly.(4). The trace function representation of the sequences of length p^m (p prime, m≥2) are investigated, from which we derived their linear complexity.(5). An examination is given to the linear complexity of some 3-ary sequences, proposed by No, of period 3ⁿ-l(n = 3ek, e, k integer) with the ideal autocorrelation property. The exact value of linear complexity k(6e)^ωis determined when theparameter r =(?), and the upper bound of the linear complexity is given whenthe other forms of the value r is taken. As a corollary, the linear complexity 2n of HKM sequences is obtained. A Maple program is designed to illustrate the validity of the results.(6). Some new q-ary sequences with period q^3ek-1 (q=p^m, p an odd prime, m, e, k integers) are constructed. Inspired by Antweiler's method, we determine their linear complexity. Our results show that this sequence has larger linear span than GMW sequence with the same parameters. Finally, the results of a Maple program are included to illustrate the validity of the results.