On the linear complexity of Legendre–Sidelnikov sequences

Abstract

Linear complexity is an important cryptographic index of sequences. We study the linear complexity of $p(q-1)$-periodic Legendre–Sidelnikov sequences, which combine the concepts of Legendre sequences and Sidelnikov sequences. We get lower and upper bounds on the linear complexity in different cases, and experiments show that the upper bounds can be attained. Remarkably, we associate the linear complexity of Legendre–Sidelnikov sequences with some famous primes including safe prime and Fermat prime. If $2$ is a primitive root modulo $\frac{q-1}{2}$, and $q$ is a safe prime greater than 7, the linear complexity is the period if $p\equiv 3 \pmod 8$; $p(q-1)-p+1$ if $p\equiv q \equiv 7 \pmod 8$, and $p(q-1)-\frac{p-1}{2}$ if $p \equiv 7 \pmod 8, q \equiv 3 \pmod 8$. If $q$ is a Fermat prime, the linear complexity is the period if $p \equiv 3 \pmod 8$, and $p(q-1)-q+2$ if $p \equiv 5 \pmod 8$. It is very interesting that the Legendre–Sidelnikov sequence has maximal linear complexity and is balanced if we choose $p=q$ to be some safe prime.