On the complexity of quaternary sequences derived from a pair of Legendre sequences

Linear complexity and $2$-adic complexity are defined as the length of the shortest linear feedback shift registers and feedback-carry shift registers that can generate the sequence, respectively. In this paper, the linear complexity and $4$-adic complexity of quaternary sequences with a period $pq$ has been studied. The sequences under consideration are derived from a pair of quaternary Legendre sequences with periods $p$ and $q$. The terms of these sequences are equal to the sum of the terms of the Legendre sequences modulo four for term number coprime with $pq$, equal to zero if the term number is divisible by $p$, and equal to $2$ in other cases. The research method is based on the use of generalized Whitman cyclotomic classes, Gaussian periods, and Hall polynomials. The following statements hold for the sequences in question: (i) the linear complexity of sequence with period $pq$ over a residue class ring modulo four is greater than $(3pq+1)/4$; (ii) the linear complexity of sequence with period $pq$ obtained from the considered quaternary sequences using Gray mapping is greater than $pq-(p+3)q/4$; (iii) the $4$-adic complexity of the sequence with period $pq$ is greater than $ pq-1-2\log_2(pq)$. Hence, these sequences have high linear complexity over a residue class ring modulo four and over a finite field of order four. The $4$-adic complexity of the sequences is sufficient to repel attacks using the rational approximation algorithm.