On the GF(p) linear complexity of Hall’s sextic sequences and some cyclotomic-set-based sequences

Abstract

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.

Keywords

Linear complexity / Hall’s sextic residues sequence / Cyclotomic set

References

[1] Massey J. L.. Shift-register synthesis and bch decoding. IEEE Transactions on Information Theory, 1969, 15(1): 122-127

[2] Klapper A.. The vulnerability of geometric sequences based on fields of odd characteristic. Journal of Cryptology, 1994, 7(1): 33-51

[3] Chen H., Xu L.. On the binary sequences with high gf(2) linear complexities and low gf(p) linear complexities. IACR Cryptology ePrint Archive, 2005, 2005: 241

[4] XU L. Q.. On gf(p)-linear complexities of binary sequences. The Journal of China Universities of Posts and Telecommunications, 2009, 16(4): 112-124

[5] He X.. On the gf(p) linear complexity of Legendre sequences. Journal on Communications, 2008, 29(3): 16-22

[6] Kim J. H., Song H. Y.. On the linear complexity of halls sextic residue sequences. IEEE Transactions on Information Theory, 2001, 47(5): 2094-2096

[7] Kim J. H., Song H. Y., Gong G.. Trace representation of Hall’s sextic residue sequences of period p = 7 (mod 8), Mathematical Properties of Sequences and Other Combinatorial Structures, 2003, New York: Springer-Verlag 23-32

[8] Dai Z., Gong G., Song H. Y., Ye D.. Trace representation and linear complexity of binary e-th power residue sequences of period. IEEE Transactions on Information Theory, 2011, 57(3): 1530-1547

[9] Dai Z., Gong G., Song H. Y.. Trace representation and linear complexity of binary e-th residue sequences. Proceedings of International Workshop on Coding and Cryptography, 2003 24-28

[10] Baumert L. D.. Cyclic Difference Sets, 1971, New York: Springer-Verlag

[11] Lazarus A. J.. The sextic period polynomial. Bulletin of the Australian Mathematical Society, 1994, 49(2): 293-304

[12] Colbourn C. J., Dinitz J. H.. Handbook of Combinatorial Designs, 2010, Boca Raton: CRC Press

[13] Ireland K., Rosen M. I.. A Classical Introduction to Modern Number Theory, 1982, Boca Raton: Springer-Verlag

[14] Ding C., Helleseth T., Lam K. Y.. Several classes of binary sequences with three-level autocorrelation. IEEE Transactions on Information Theory, 1999, 45(7): 2606-2612

[15] Hu L., Yue Q., Wang M.. The linear complexity of whitemans generalized cyclotomic sequences of period. IEEE Transactions on Information Theory, 2012, 58(8): 5534-5543