Linear complexity over ${\mathbb{F}}_q$ and 2-adic complexity of a class of binary generalized cyclotomic sequences with low-value autocorrelation

Abstract

A class of binary sequences with period $2p$ is constructed using generalized cyclotomic classes, and their linear complexity, minimal polynomial over ${\mathbb{F}}_q$ as well as 2-adic complexity are determined using Gauss period and group ring theory. The results show that the linear complexity of these sequences attains the maximum when $p\equiv \pm 1(\mathrm{mod}8)$ and is equal to {$p$+1} when $p\equiv \pm 3(\mathrm{mod}8)$ over extension field. Moreover, the 2-adic complexity of these sequences is maximum. According to Berlekamp-Massey(B-M) algorithm and the rational approximation algorithm(RAA), these sequences have quite good cryptographyic properties in the aspect of linear complexity and 2-adic complexity.

23 pages