main-content

Erschienen in:

11.04.2018

A lower bound on the 2-adic complexity of the modified Jacobi sequence

verfasst von: Yuhua Sun, Qiang Wang, Tongjiang Yan

Erschienen in: Cryptography and Communications | Ausgabe 2/2019

Einloggen, um Zugang zu erhalten

Abstract

Let p, q be distinct primes satisfying gcd(p −  1, q −  1) = d and let Di, i =  0, 1, · · · ,d −  1, be Whiteman’s generalized cyclotomic classes with $$\mathbb {Z}_{pq}^{\ast }=\cup _{i = 0}^{d-1}D_{i}$$. In this paper, we give the values of Gauss periods based on the generalized cyclotomic sets $$D_{0}^{\ast }=\cup _{i = 0}^{\frac {d}{2}-1}D_{2i}$$ and $$D_{1}^{\ast }=\cup _{i = 0}^{\frac {d}{2}-1}D_{2i + 1}$$. As an application, we determine a lower bound on the 2-adic complexity of the modified Jacobi sequence. Our result shows that the 2-adic complexity of the modified Jacobi sequence is at least pqpq − 1 with period N = pq. This indicates that the 2-adic complexity of the modified Jacobi sequence is large enough to resist the attack of the rational approximation algorithm (RAA) for feedback with carry shift registers (FCSRs).
Literatur
1.
Bai, E., Liu, X., Xiao, G.: Linear complexity of new generalized cyclotomic sequences of order two of length pq. IEEE Trans. Inform. Theory 51, 1849–1853 (2005)
2.
Cai, H., Liang, H., Tang, X.: Constructions of optimal 2-D optical orthogonal codes via generalized cyclotomic classes. IEEE Trans. Inform. Theory 61, 688–695 (2015)
3.
Chen, Z., Du, X., Xiao, G.: Sequences related to Legendre/Jacobi sequences. Inf. Sci. 177(21), 4820–4831 (2007)
4.
Cusick, T.W., Ding, C, Renvall, A.: Stream ciphers and number theory. Elsevier, Amsterdam (2015) MATH
5.
Davis, P.J.: Circulant matrices. Chelsea, New York (1994) MATH
6.
Ding, C., Xing, C.: Several classes of (2 m − 1, w, 2) optical orthogonal codes. Discret. Appl. Math. 128, 103–120 (2003)
7.
Ding, C., Xing, C.: Cyclotomic optical orthogonal codes of composite lengths. IEEE Trans. Inform. Theory 52, 263–268 (2004)
8.
Ding, C.: Cyclotomic constructions of cyclic codes with length being the product of two primes. IEEE Trans. Inform. Theory 58, 2231–2236 (2012)
9.
Ding, C.: Cyclic codes from the two-prime sequences. IEEE Trans. Inform. Theory 58, 3881–3891 (2012)
10.
Ding, C., Helleseth, T.: On the linear complexity of Legendre sequences. IEEE Trans. Inform. Theory 44, 1693–1698 (1998)
11.
Fan, C., Ge, G.: A unified approach to Whiteman’s and Ding-Helleseth’s generalized cyclotomy over residue class rings. IEEE Trans. Inf. Theory 60, 1326–1336 (2014)
12.
Green, D.H., Green, P.R.: Modified Jacobi sequences. IEEE Proceedings-Computers and Digital Techniques 147(4), 241–251 (2000) CrossRef
13.
Green, D.H., Choi, J.: Linear complexity of modified Jacobi sequences. IEE Proceedings-Computers and Digital Techniques 149(3), 97–101 (2002) CrossRef
14.
Hu, L., Yue, Q.: Gauss periods and codebooks from generalized cyclotomic sets of order four. Des. Codes Crypt. 69, 233–246 (2013)
15.
Li, X., Ma, W., Yan, T., Zhao, X.: Linear complexity of a new generalized cyclotomic sequence of order two of length pq. IEICE Trans. 96-A, 1001–1005 (2013) CrossRef
16.
Massey, J.L.: Shift-register synthesis and BCH decoding. IEEE Trans. Inform. Theory 15, 122–127 (1969)
17.
Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol. 10, 111–147 (1997)
18.
Tang, X., Ding, C.: New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation Value. IEEE Trans. Inform. Theory 56, 6398–6405 (2010)
19.
Tang, X., Fan, P., Matsufuji, S.: Lower bounds on the maximum correlation of sequences with low or zero correlation zone. Electron. Lett. 36, 551–552 (2000) CrossRef
20.
Tian, T., Qi, W.: 2-Adic complexity of binary m-sequences. IEEE Trans. Inform. Theory 56, 450–454 (2010)
21.
Whiteman, A.L.: A family of difference sets. Ill. J. Math. 6, 107–121 (1962)
22.
Xiong, H., Qu, L., Li, C.: A new method to compute the 2-adic complexity of binary sequences. IEEE Trans. Inform. Theory 60, 2399–2406 (2014)
23.
Xiong, H., Qu, L., Li, C.: 2-Adic complexity of binary sequences with interleaved structure. Finite Fields Appl. 33, 14–28 (2015)
24.
Yan, T.: Study on constructions and properties of pseudo-random sequence. Ph. D Thesis (2007)
25.
Xiong, T., Hall, J.I.: Modifications of modified Jacobi sequences. IEEE Trans. Inform. Theory 57, 493–504 (2011)
26.
Yan, T., Du, X., Xiao, G., Huang, X.: Linear complexity of binary Whiteman generalized cyclotomic sequences of order 2 k. Inf. Sci. 179, 1019–1023 (2009)
27.
Zeng, X., Cai, H., Tang, X., Yang, Y.: Optimal frequency sequences of odd length. IEEE Trans. Inform. Theory 59, 3237–3248 (2013)
28.
Xiao, Z., Zeng, X., Sun, Z.: 2-Adic complexity of two classes of generalized cyclotomic binary sequences. Int. J. Found. Comput. Sci. 27, 879–893 (2016)
29.
Zhou, Z., Tang, X., Gong, G.: A new classes of sequences with zero or low correlation zone based on interleaving technique. IEEE Trans. Inform. Theory 54, 4267–4273 (2008)
Titel
A lower bound on the 2-adic complexity of the modified Jacobi sequence
verfasst von
Yuhua Sun
Qiang Wang
Tongjiang Yan
Publikationsdatum
11.04.2018
Verlag
Springer US
Erschienen in
Cryptography and Communications / Ausgabe 2/2019
Print ISSN: 1936-2447
Elektronische ISSN: 1936-2455
DOI
https://doi.org/10.1007/s12095-018-0300-y

Zur Ausgabe