In this survey we summarize properties of pseudorandomness and non-randomness of some number-theoretic sequences and present results on their behaviour under the following measures of pseudorandomness: balance, linear complexity, correlation measure of order k, expansion complexity and 2-adic complexity. The number-theoretic sequences are the Legendre sequence and the two-prime generator, the Thue-Morse sequence and its sub-sequence along squares, and the prime omega sequences for integers and polynomials.

Periodic sequences, used as keys in cryptosystems, plays an important role in cryptography. Such periodic sequences should possess high linear complexity to resist B-M algorithm. Sequences constructed by cyclotomic cosets have been widely studied in the past few years. In this paper, the linear complexity of n-periodic cyclotomic sequences of order 2 and 4 over 𝔽p has been calculated, where n and p are two distinct odd primes. The conclusions reveal that the presented sequences have high linear complexity in many cases, which indicates that the sequences can resist the linear attack.

We found that the work of Kim et al. [1] on trace representation of the Legendre sequence with the periods p ≡ ±3 (mod 8) can be improved by restricting the selection of the periods p while maintaining the form p ≡ ±3 (mod 8) unchanged. Our method relies on forcing the multiplicative group of residue classes modulo p, Zp*, to take 2 as the least primitive root. On the other hand, by relaxing the very strong condition in the theorem of these authors and by using the product among powers of the primitive root and powers of any quadratic residue element to represent an element in Zp*, we could extend Kim's formula so that it becomes a special case of our formula more general.

In this paper, the linear complexity and minimal polynomials of Legendre sequences over Fq have been calculated, where q = pm and p is a prime number. Our results show that Legendre sequences have high linear complexity over Fq for a large part of prime power number q so that they can resist the linear attack method.

In this paper, for an odd prime p, new quaternary sequences of even period 2p with ideal autocorrelation property are constructed using the binary Legendre sequences of period p. For the new quaternary sequences, two properties which are considered as the major characteristics of pseudo-random sequences are derived. Firstly, the autocorrelation distribution of the proposed quaternary sequences is derived and it is shown that the autocorrelation values of the proposed quaternary sequences are optimal. For both p≡1 mod 4 and p≡3 mod 4, we can construct optimal quaternary sequences while only for p≡3 mod 4, the binary Legendre sequences can satisfy ideal autocorrelation property. Secondly, the linear complexity of the proposed quaternary sequences is also derived by counting non-zero coefficients of the discrete Fourier transform over the finite field Fq which is the splitting field of x2p-1. It is shown that the linear complexity of the quaternary sequences is larger than or equal to p or (3p+1)/2 for p≡1 mod 4 or p≡3 mod 4, respectively.

Binary sequences with two-level periodic autocorrelation correspond directly to cyclic (v, k, λ)-designs. When v = 4t-1, k = 2t -1 and λ = t-1, for some positive integer t, the sequence (or design) is called a cyclic Hadamard sequence (or design). For all known examples, v is either a prime number, a product of twin primes, or one less than a power of 2. Except when v = 2k-1, all known examples are based on quadratic residues (using the Legendre symbol when v is prime, and the Jacobi symbol when v = p(p+2) where both p and p+2 are prime); or sextic residues (when v is a prime of the form 4a2 + 27). However, when v = 2k-1, many constructions are now known, including m-sequences (corresponding to Singer difference sets), quadratic and sextic residue sequences (when 2k-1 is prime), GMW sequences and their generalizations (when k is composite), certain term-by-term sums of three and of five m-sequences and more general sums of trace terms, several constructions based on hyper-ovals in finite geometries (found by Segre, by Glynn, and by Maschietti), and the result of performing the Welch-Gong transformation on some of the foregoing.