Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Cryptography and Communications 2/2019

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
share
TEILEN

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.
Zurück zum Zitat 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) MathSciNetCrossRefMATH 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) MathSciNetCrossRefMATH
2.
Zurück zum Zitat 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) MathSciNetCrossRefMATH 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) MathSciNetCrossRefMATH
4.
Zurück zum Zitat Cusick, T.W., Ding, C, Renvall, A.: Stream ciphers and number theory. Elsevier, Amsterdam (2015) MATH Cusick, T.W., Ding, C, Renvall, A.: Stream ciphers and number theory. Elsevier, Amsterdam (2015) MATH
5.
Zurück zum Zitat Davis, P.J.: Circulant matrices. Chelsea, New York (1994) MATH Davis, P.J.: Circulant matrices. Chelsea, New York (1994) MATH
6.
Zurück zum Zitat Ding, C., Xing, C.: Several classes of (2 m − 1, w, 2) optical orthogonal codes. Discret. Appl. Math. 128, 103–120 (2003) CrossRefMATH Ding, C., Xing, C.: Several classes of (2 m − 1, w, 2) optical orthogonal codes. Discret. Appl. Math. 128, 103–120 (2003) CrossRefMATH
7.
Zurück zum Zitat Ding, C., Xing, C.: Cyclotomic optical orthogonal codes of composite lengths. IEEE Trans. Inform. Theory 52, 263–268 (2004) Ding, C., Xing, C.: Cyclotomic optical orthogonal codes of composite lengths. IEEE Trans. Inform. Theory 52, 263–268 (2004)
8.
Zurück zum Zitat Ding, C.: Cyclotomic constructions of cyclic codes with length being the product of two primes. IEEE Trans. Inform. Theory 58, 2231–2236 (2012) MathSciNetCrossRefMATH Ding, C.: Cyclotomic constructions of cyclic codes with length being the product of two primes. IEEE Trans. Inform. Theory 58, 2231–2236 (2012) MathSciNetCrossRefMATH
10.
Zurück zum Zitat Ding, C., Helleseth, T.: On the linear complexity of Legendre sequences. IEEE Trans. Inform. Theory 44, 1693–1698 (1998) MathSciNetCrossRef Ding, C., Helleseth, T.: On the linear complexity of Legendre sequences. IEEE Trans. Inform. Theory 44, 1693–1698 (1998) MathSciNetCrossRef
11.
Zurück zum Zitat 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) MathSciNetCrossRefMATH 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) MathSciNetCrossRefMATH
12.
Zurück zum Zitat Green, D.H., Green, P.R.: Modified Jacobi sequences. IEEE Proceedings-Computers and Digital Techniques 147(4), 241–251 (2000) CrossRef Green, D.H., Green, P.R.: Modified Jacobi sequences. IEEE Proceedings-Computers and Digital Techniques 147(4), 241–251 (2000) CrossRef
13.
Zurück zum Zitat Green, D.H., Choi, J.: Linear complexity of modified Jacobi sequences. IEE Proceedings-Computers and Digital Techniques 149(3), 97–101 (2002) CrossRef Green, D.H., Choi, J.: Linear complexity of modified Jacobi sequences. IEE Proceedings-Computers and Digital Techniques 149(3), 97–101 (2002) CrossRef
14.
Zurück zum Zitat Hu, L., Yue, Q.: Gauss periods and codebooks from generalized cyclotomic sets of order four. Des. Codes Crypt. 69, 233–246 (2013) MathSciNetCrossRefMATH Hu, L., Yue, Q.: Gauss periods and codebooks from generalized cyclotomic sets of order four. Des. Codes Crypt. 69, 233–246 (2013) MathSciNetCrossRefMATH
15.
Zurück zum Zitat 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 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
17.
Zurück zum Zitat Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol. 10, 111–147 (1997) MathSciNetCrossRefMATH Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. J. Cryptol. 10, 111–147 (1997) MathSciNetCrossRefMATH
18.
Zurück zum Zitat 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) MathSciNetCrossRefMATH 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) MathSciNetCrossRefMATH
19.
Zurück zum Zitat 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 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
22.
Zurück zum Zitat 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) MathSciNetCrossRefMATH 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) MathSciNetCrossRefMATH
23.
Zurück zum Zitat Xiong, H., Qu, L., Li, C.: 2-Adic complexity of binary sequences with interleaved structure. Finite Fields Appl. 33, 14–28 (2015) MathSciNetCrossRefMATH Xiong, H., Qu, L., Li, C.: 2-Adic complexity of binary sequences with interleaved structure. Finite Fields Appl. 33, 14–28 (2015) MathSciNetCrossRefMATH
24.
Zurück zum Zitat Yan, T.: Study on constructions and properties of pseudo-random sequence. Ph. D Thesis (2007) Yan, T.: Study on constructions and properties of pseudo-random sequence. Ph. D Thesis (2007)
25.
26.
Zurück zum Zitat 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) CrossRefMATH 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) CrossRefMATH
27.
Zurück zum Zitat Zeng, X., Cai, H., Tang, X., Yang, Y.: Optimal frequency sequences of odd length. IEEE Trans. Inform. Theory 59, 3237–3248 (2013) MathSciNetCrossRefMATH Zeng, X., Cai, H., Tang, X., Yang, Y.: Optimal frequency sequences of odd length. IEEE Trans. Inform. Theory 59, 3237–3248 (2013) MathSciNetCrossRefMATH
28.
Zurück zum Zitat 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) MathSciNetCrossRefMATH 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) MathSciNetCrossRefMATH
29.
Zurück zum Zitat 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) MathSciNetCrossRefMATH 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) MathSciNetCrossRefMATH
Metadaten
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

Weitere Artikel der Ausgabe 2/2019

Cryptography and Communications 2/2019 Zur Ausgabe

Premium Partner