On the GF(p) Linear Complexity of Hall's Sextic Sequences and Some Cyclotomic-Set-Based Sequences

Klapper (1994) showed that there exists a class of geometric sequences with the maximal possible linear complexity when considered as sequences over GF(2), but these sequences have very low linear complexities when considered as sequences over GF(p) (p is an odd prime). This linear complexity of a binary sequence when considered as a sequence over GF(p) is called GF(p) complexity. This indicates that the binary sequences with high GF(2) linear complexities are inadequate for security in the practical application, while, their GF(p) linear complexities are also equally important, even when the only concern is with attacks using the Berlekamp-Massey algorithm [Massey, J. L., Shift-register synthesis and bch decoding, IEEE Transactions on Information Theory, 15(1), 1969, 122-127]. From this perspective, in this paper the authors study the GF(p) linear complexity of Hall's sextic residue sequences and some known cyclotomic-set-based sequences.