GLS: New class of generalized Legendre sequences with optimal arithmetic cross-correlation
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 47 (2013) no. 4, p. 371-388

The Legendre symbol has been used to construct sequences with ideal cross-correlation, but it was never used in the arithmetic cross-correlation. In this paper, a new class of generalized Legendre sequences are described and analyzed with respect to their period, distributional, arithmetic cross-correlation and distinctness properties. This analysis gives a new approach to study the connection between the Legendre symbol and the arithmetic cross-correlation. In the end of this paper, possible application of these sequences with optimal arithmetic cross-correlation is indicated.

DOI : https://doi.org/10.1051/ita/2013043
Classification:  11T71,  14G50,  94A60
Keywords: arithmetic cross-correlation, Legendre symbol, primitive sequence, cyclically distinct
@article{ITA_2013__47_4_371_0,
     author = {WANG, Huijuan and WEN, Qiaoyan and ZHANG, Jie},
     title = {GLS: New class of generalized Legendre sequences with optimal arithmetic cross-correlation},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {4},
     year = {2013},
     pages = {371-388},
     doi = {10.1051/ita/2013043},
     mrnumber = {3132297},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2013__47_4_371_0}
}
WANG, Huijuan; WEN, Qiaoyan; ZHANG, Jie. GLS: New class of generalized Legendre sequences with optimal arithmetic cross-correlation. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 47 (2013) no. 4, pp. 371-388. doi : 10.1051/ita/2013043. http://www.numdam.org/item/ITA_2013__47_4_371_0/

[1] M. Goresky and A. Klapper, Arithmetic crosscorrelations of feedback with carry shift register sequences. IEEE Trans. Inform. Theory 43 (1997) 1342-C1345. | MR 1454969 | Zbl 0878.94047

[2] Hong Xu, Wen-Feng Qi, Further results on the distinctness of decimations of l-sequences. IEEE Trans. Inform. Theory 52 (2006) 3831-3836. | MR 2245132 | Zbl 1213.94072

[3] A. Klapper and M. Goresky, Arithmetic correlations and Walsh transforms. IEEE Trans. Inform. Theory 58 (2012) 479-492. | MR 2907735

[4] Qun-Xiong Zheng and Wen-Feng Qi, Distribution properties of compressing sequences derived from primitive sequence over Z / (pe). IEEE Trans. Inform. Theory 56 (2010) 479-492. | MR 2589464

[5] X.Y. Zhu and Wen-Feng Qi, Uniqueness of the distribution of zeroes of primitive level sequences over Z / (pe). Finite Fields 11 (2005) 30-44. | MR 2111896 | Zbl 1092.11047

[6] J.-H. Kim and H.-Y. Song, Trace representation of Legendre sequences. Designs. Codes and Cryptography 24 (2001) 343-348. | MR 1857147 | Zbl 0991.94031

[7] M. Goresky and A. Klapper, Fibonacci and Galois representations of feedback-with-carry shift registers. IEEE Trans. Inform. Theory 48 (2002) 2826-2836. | MR 1945576 | Zbl 1062.94028

[8] Fan ShuFan Shu-qin and Han Wen-bao, Distribution of elements in primitive sequences over Z / (pe). J. Math. Res. Exposition 24 (2004) 219-224. | MR 2063691 | Zbl 1142.11378

[9] A. Klapper and M. Goresky, Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptology 10 (1997) 111-147. | MR 1447843 | Zbl 0874.94029

[10] D. Mandelbaum, Arithmetic codes with large distance. IEEE Trans. Inform. Theory IT-13 (1967) 237-242. | Zbl 0171.14802

[11] Hong Xu and Wen-Feng Qi, Autocorrelations of maximum period FCSR sequence. Soc. Infustrial Appl. Math. 20 (2006) 568-577. | MR 2272213 | Zbl 1128.94006

[12] M. Goresky and A. Klapper, Statistical Properties of the Arithmetic Correlation of Sequences. Internat. J. Found. Comput. Sci. 22 (2011) 1297-1315. | MR 2835831 | Zbl 1236.94045

[13] Tian Tian and Wen-Feng Qi, 2-Adic Complexity of Binary m-sequences. IEEE Trans. Inf. Theory 56 (2010) 450-454. | MR 2589456

[14] Huijuan Wang, Qiaoyan Wen and Jie Zhang, 2-Adic Complexity of Self-shrinking Sequence. IEEE Trans. Fundamentals E94-A (2011) 11.

[15] R.A. Rueppel, Analysis and Design of Stream ciphers (Communications and Control Engineering Series). Springer-Verlag, Berlin, Germany (1986). | MR 861124 | Zbl 0618.94001

[16] R. Lidl and H. Niederriter, Finite Fields. Reading MA: Addison-Wesley (1983). | Zbl 0554.12010

[17] Tian Tian and Wen-Feng Qi, Autocorrelation and distinctness of decimations of l-sequences based on primes. Soc. Industrial Appl. Math. 23 (2009) 805-821. | MR 2496919 | Zbl 1215.11004

[18] Th.W. Cusick, Cunsheng Ding, Ari Renvall, Stream Ciphers and Number Theory. Language Arts and Disciplines (1998). | MR 1634586 | Zbl 0930.11086