main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.03.2015 | Ausgabe 3/2015

# On the linear complexity of Legendre–Sidelnikov sequences

Zeitschrift:
Designs, Codes and Cryptography > Ausgabe 3/2015
Autor:
Ming Su
Wichtige Hinweise
Communicated by A. Winterhof.

## 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.

### Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Literatur
Über diesen Artikel

Zur Ausgabe