Jing et al. dealed with all possible Whiteman generalized cyclotomic binary sequences $ s(a, b, c) $ with period $ N = pq $, where $ (a, b, c) \in \{0, 1\}^3 $ and $ p, q $ are distinct odd primes (Jing et al. arXiv:2105.10947v1, 2021). They have determined the autocorrelation distribution and the 2-adic complexity of these sequences in a unified way by using group ring language and a version of quadratic Gauss sums. In this paper, we determine the linear complexity and the 1-error linear complexity of $ s(a, b, c) $ in details by using the discrete Fourier transform (DFT). The results indicate that the linear complexity of $ s(a, b, c) $ is large enough and stable in most cases.
Citation: Tongjiang Yan, Pazilaiti Ainiwaer, Lianbo Du. On the 1-error linear complexity of two-prime generator[J]. AIMS Mathematics, 2022, 7(4): 5821-5829. doi: 10.3934/math.2022322
Jing et al. dealed with all possible Whiteman generalized cyclotomic binary sequences $ s(a, b, c) $ with period $ N = pq $, where $ (a, b, c) \in \{0, 1\}^3 $ and $ p, q $ are distinct odd primes (Jing et al. arXiv:2105.10947v1, 2021). They have determined the autocorrelation distribution and the 2-adic complexity of these sequences in a unified way by using group ring language and a version of quadratic Gauss sums. In this paper, we determine the linear complexity and the 1-error linear complexity of $ s(a, b, c) $ in details by using the discrete Fourier transform (DFT). The results indicate that the linear complexity of $ s(a, b, c) $ is large enough and stable in most cases.
| [1] | T. Cusick, C. Ding, A. Renvall, Stream ciphers and number theory, Amsterdam: Elsevier, 2004. |
| [2] | C. Ding, G. Xiao, W. Shan, The stability theory of stream ciphers, Berlin: Springer, 1991. http://dx.doi.org/10.1007/3-540-54973-0 |
| [3] |
M. Stamp, C. Martin, An algorithm for the $k$-error linear complexity of binary sequences with period $2^n$, IEEE Trans. Inform. Theory, 39 (1993), 1398–1401. http://dx.doi.org/10.1109/18.243455 doi: 10.1109/18.243455
|
| [4] |
R. Blahut, Transform techniques for error control codes, IBM J. Res. Dev., 23 (1979), 299–315. http://dx.doi.org/10.1147/rd.233.0299 doi: 10.1147/rd.233.0299
|
| [5] | F. MacWilliams, N. Sloane, The theory of error-correcting codes, Amsterdam: Elsevier, 1977. |
| [6] |
C. Ding, Linear complexity of generalized cyclotomic binary sequences of order 2, Finite Fields Th. Appl., 3 (1997), 159–174. http://dx.doi.org/10.1006/ffta.1997.0181 doi: 10.1006/ffta.1997.0181
|
| [7] |
C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Inform. Theory, 44 (1998), 1699–1702. http://dx.doi.org/10.1109/18.681354 doi: 10.1109/18.681354
|
| [8] |
X. Li, W. Ma, T. Yan, X. Zhao, Linear complexity of a new generalized cyclotomic sequence of order two of length $pq$, IEICE Trans. Fund. Elect., 96 (2013), 1001–1005. http://dx.doi.org/10.1587/transfun.E96.A.1001 doi: 10.1587/transfun.E96.A.1001
|
| [9] | Y. Wei, 1, 2-error linear complexity of Legendre sequences (Chinese), Master's Thesis, Hubei University, 2015. |
| [10] |
R. Hofer, A. Winterhof, On the 2-adic complexity of the two-prime generator, IEEE Trans. Inform. Theory, 64 (2018), 5957–5960. http://dx.doi.org/10.1109/TIT.2018.2811507 doi: 10.1109/TIT.2018.2811507
|
| [11] | A. Alecu, A. Sălăgean, An approximation algorithm for computing the $k$-error linear complexity of sequences using the discrete fourier transform, Proceedings of IEEE International Symposium on Information Theory, 2008, 2414–2418. http://dx.doi.org/10.1109/ISIT.2008.4595424 |
| [12] |
Z. Chen, C. Wu, $K$-error linear complexity of binary cyclotomic generators, Journal on Communications, 40 (2019), 197–206. http://dx.doi.org/10.11959/j.issn.1000-436x.2019034 doi: 10.11959/j.issn.1000-436x.2019034
|
| [13] |
X. Zhou, Cyclic codes via the general two-prime generalized cyclotomic sequence of order two, J. Math., 2020 (2020), 6625652. http://dx.doi.org/10.1155/2020/6625652 doi: 10.1155/2020/6625652
|
| [14] | X. Jing, S. Qing, M. Yang, K. Feng, Determination of the autocorrelation distribution and 2-adic complexity of generalized cyclotomic binary sequences of order 2 with period $pq$, arXiv: 2105.10947. |
| [15] |
A. Whiteman, A family of defference sets, Illinois J. Math., 6 (1962), 107–121. http://dx.doi.org/10.1215/ijm/1255631810 doi: 10.1215/ijm/1255631810
|
| [16] |
C. Ding, Cyclotomic constructions of cyclic codes with length being the product of two primes, IEEE Trans. Inform. Theory, 58 (2012), 2231–2236. http://dx.doi.org/10.1109/TIT.2011.2176915 doi: 10.1109/TIT.2011.2176915
|
Tongjiang Yan, Pazilaiti Ainiwaer, Lianbo Du. On the 1-error linear complexity of two-prime generator[J]. AIMS Mathematics, 2022, 7(4): 5821-5829. doi: 10.3934/math.2022322
DownLoad: