Skip to main content
Top
Published in:

07-09-2022 | Original Paper

Balance, pattern distribution and linear complexity of M-ary sequences from Sidel’nikov sequences

Authors: Huaning Liu, Yixin Ren

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 5/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Kim, Chung, No and Chung introduced new families of M-ary sequences by using Sidel’nikov sequences and the shift-and-add method. Chung, No and Chung constructed more families of M-ary sequences based on Sidel’nikov sequences and the shift-and-inverse method. In this paper we further study the balancedness of these sequences and show that they have asymptotical uniform pattern distributions under some assumptions on the parameters of the sequences. Linear complexity profiles of the sequences are also studied.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Alaca, S., Millar, G.: Character values of the Sidelnikov–Lempel–Cohn–Eastman sequences. Cryptogr. Commun. 9(6), 665–682 (2017)MathSciNetCrossRef Alaca, S., Millar, G.: Character values of the Sidelnikov–Lempel–Cohn–Eastman sequences. Cryptogr. Commun. 9(6), 665–682 (2017)MathSciNetCrossRef
2.
go back to reference Alaca, S., Millar, G.: Shift-inequivalent decimations of the Sidelnikov–Lempel–Cohn–Eastman sequences. Des. Codes Cryptogr. 88(3), 567–583 (2020)MathSciNetCrossRef Alaca, S., Millar, G.: Shift-inequivalent decimations of the Sidelnikov–Lempel–Cohn–Eastman sequences. Des. Codes Cryptogr. 88(3), 567–583 (2020)MathSciNetCrossRef
3.
go back to reference Aly, H., Meidl, W.: On the linear complexity and \(k\)-error linear complexity over \({\mathbb{F} }_p\) of the \(d\)-ary Sidelnikov sequence. IEEE Trans. Inf. Theory 53(12), 4755–4761 (2007)CrossRef Aly, H., Meidl, W.: On the linear complexity and \(k\)-error linear complexity over \({\mathbb{F} }_p\) of the \(d\)-ary Sidelnikov sequence. IEEE Trans. Inf. Theory 53(12), 4755–4761 (2007)CrossRef
4.
go back to reference Aly, H., Winterhof, A.: On the \(k\)-error linear complexity over \({\mathbb{F} }_p\) of Legendre and Sidelnikov sequences. Des. Codes Cryptogr. 40(3), 369–374 (2006)MathSciNetCrossRef Aly, H., Winterhof, A.: On the \(k\)-error linear complexity over \({\mathbb{F} }_p\) of Legendre and Sidelnikov sequences. Des. Codes Cryptogr. 40(3), 369–374 (2006)MathSciNetCrossRef
5.
go back to reference Brandstätter, N., Meidl, W.: On the linear complexity of Sidelnikov sequences over \({\mathbb{F}}_d\). In: Proceedings of SETA’06, Lecture Notes in Comput. Sci., vol. 4086, pp. 47–60. Springer, Berlin, Heidelberg (2006) Brandstätter, N., Meidl, W.: On the linear complexity of Sidelnikov sequences over \({\mathbb{F}}_d\). In: Proceedings of SETA’06, Lecture Notes in Comput. Sci., vol. 4086, pp. 47–60. Springer, Berlin, Heidelberg (2006)
6.
go back to reference Brandstätter, N., Meidl, W.: On the linear complexity of Sidelnikov sequences over nonprime fields. J. Complex. 24(5–6), 648–659 (2008)MathSciNetCrossRef Brandstätter, N., Meidl, W.: On the linear complexity of Sidelnikov sequences over nonprime fields. J. Complex. 24(5–6), 648–659 (2008)MathSciNetCrossRef
7.
go back to reference Chung, J., Kim, Y., Lim, T., No, J., Chung, H.: On some properties of \(M\)-ary Sidelnikov sequences. IEICE Trans. Fundam. E92–A(1), 342–345 (2009)CrossRef Chung, J., Kim, Y., Lim, T., No, J., Chung, H.: On some properties of \(M\)-ary Sidelnikov sequences. IEICE Trans. Fundam. E92–A(1), 342–345 (2009)CrossRef
8.
go back to reference Chung, J., No, J., Chung, H.: A construction of a new family of \(M\)-ary sequences with low correlation from Sidelnikov sequences. IEEE Trans. Inf. Theory 57(4), 2301–2305 (2011)CrossRef Chung, J., No, J., Chung, H.: A construction of a new family of \(M\)-ary sequences with low correlation from Sidelnikov sequences. IEEE Trans. Inf. Theory 57(4), 2301–2305 (2011)CrossRef
9.
go back to reference Chung, J., Yang, K.: Bounds on the linear complexity and the 1-error linear complexity over \({\mathbb{F}}_p\) of \(M\)-ary Sidelnikov sequences. In: Proceedings of SETA’06, Lecture Notes in Comput. Sci., vol. 4086, pp. 74–87. Springer, Berlin, Heidelberg (2006) Chung, J., Yang, K.: Bounds on the linear complexity and the 1-error linear complexity over \({\mathbb{F}}_p\) of \(M\)-ary Sidelnikov sequences. In: Proceedings of SETA’06, Lecture Notes in Comput. Sci., vol. 4086, pp. 74–87. Springer, Berlin, Heidelberg (2006)
10.
go back to reference Eun, Y., Song, H., Kyureghyan, G.: One-error linear complexity over Fp of Sidelnikov sequences. In: Proc. Int. Conf. Sequ. Appl., Seoul 2004, Lecture Notes in Comput. Sci., vol. 3486, pp. 154–165. Springer, Berlin, Heidelberg (2005) Eun, Y., Song, H., Kyureghyan, G.: One-error linear complexity over Fp of Sidelnikov sequences. In: Proc. Int. Conf. Sequ. Appl., Seoul 2004, Lecture Notes in Comput. Sci., vol. 3486, pp. 154–165. Springer, Berlin, Heidelberg (2005)
11.
go back to reference Garaev, M.Z., Luca, F., Shparlinski, I.E., Winterhof, A.: On the lower bound of the linear complexity over \({\mathbb{F} }_p\) of Sidelnikov sequences. IEEE Trans. Inf. Theory 52(7), 3299–3304 (2006)CrossRef Garaev, M.Z., Luca, F., Shparlinski, I.E., Winterhof, A.: On the lower bound of the linear complexity over \({\mathbb{F} }_p\) of Sidelnikov sequences. IEEE Trans. Inf. Theory 52(7), 3299–3304 (2006)CrossRef
12.
go back to reference Han, Y.K., Yang, K.: New \(M\)-ary sequence families with low correlation and large size. IEEE Trans. Inf. Theory 55(4), 1815–1823 (2009)MathSciNetCrossRef Han, Y.K., Yang, K.: New \(M\)-ary sequence families with low correlation and large size. IEEE Trans. Inf. Theory 55(4), 1815–1823 (2009)MathSciNetCrossRef
13.
go back to reference He, J.J., Panario, D., Wang, Q., Winterhof, A.: Linear complexity profile and correlation measure of interleaved sequences. Cryptogr. Commun. 7(4), 497–508 (2015)MathSciNetCrossRef He, J.J., Panario, D., Wang, Q., Winterhof, A.: Linear complexity profile and correlation measure of interleaved sequences. Cryptogr. Commun. 7(4), 497–508 (2015)MathSciNetCrossRef
14.
go back to reference Helleseth, T., Kim, S., No, J.: Linear complexity over \({\mathbb{F} }_p\) and trace representation of Lempel–Cohn–Eastman sequences. IEEE Trans. Inf. Theory 49(6), 1548–1552 (2003)CrossRef Helleseth, T., Kim, S., No, J.: Linear complexity over \({\mathbb{F} }_p\) and trace representation of Lempel–Cohn–Eastman sequences. IEEE Trans. Inf. Theory 49(6), 1548–1552 (2003)CrossRef
15.
go back to reference Helleseth, T., Maas, M., Mathiassen, J.E., Segers, T.: Linear complexity over \({\mathbb{F} }_p\) of Sidelnikov sequences. IEEE Trans. Inf. Theory 50(10), 2468–2472 (2004)CrossRef Helleseth, T., Maas, M., Mathiassen, J.E., Segers, T.: Linear complexity over \({\mathbb{F} }_p\) of Sidelnikov sequences. IEEE Trans. Inf. Theory 50(10), 2468–2472 (2004)CrossRef
16.
go back to reference Kim, Y., Chung, J., No, J., Chung, H.: On the autocorrelation distributions of Sidelnikov sequences. IEEE Trans. Inf. Theory 51(9), 3303–3307 (2005)MathSciNetCrossRef Kim, Y., Chung, J., No, J., Chung, H.: On the autocorrelation distributions of Sidelnikov sequences. IEEE Trans. Inf. Theory 51(9), 3303–3307 (2005)MathSciNetCrossRef
17.
go back to reference Kim, Y., Chung, J., No, J., Chung, H.: On the linear complexity over \({\mathbb{F}}_p\) of \(M\)-ary Sidelnikov sequences. In: Proc. IEEE ISIT 2005, Sept., pp. 2007–2011 (2005) Kim, Y., Chung, J., No, J., Chung, H.: On the linear complexity over \({\mathbb{F}}_p\) of \(M\)-ary Sidelnikov sequences. In: Proc. IEEE ISIT 2005, Sept., pp. 2007–2011 (2005)
18.
go back to reference Kim, Y., Chung, J., No, J., Chung, H.: Linear complexity over \({\mathbb{F}}_p\) of ternary Sidelnikov sequences. In: Proceedings of SETA’06, Lecture Notes in Comput. Sci., vol. 4086, pp. 61–73. Springer, Berlin, Heidelberg (2006) Kim, Y., Chung, J., No, J., Chung, H.: Linear complexity over \({\mathbb{F}}_p\) of ternary Sidelnikov sequences. In: Proceedings of SETA’06, Lecture Notes in Comput. Sci., vol. 4086, pp. 61–73. Springer, Berlin, Heidelberg (2006)
19.
go back to reference Kim, Y., Chung, J., No, J., Chung, H.: New families of \(M\)-ary sequences with low correlation constructed from Sidelnikov sequences. IEEE Trans. Inf. Theory 54(8), 3768–3774 (2008)MathSciNetCrossRef Kim, Y., Chung, J., No, J., Chung, H.: New families of \(M\)-ary sequences with low correlation constructed from Sidelnikov sequences. IEEE Trans. Inf. Theory 54(8), 3768–3774 (2008)MathSciNetCrossRef
20.
go back to reference Kim, Y., Kim, D., Song, H.: Some properties of 2-dimensional array structure of Sidelnikov sequences of period \(q^{d}-1\). In: Proceedings of IWSDA’13, pp. 20–23 (2013) Kim, Y., Kim, D., Song, H.: Some properties of 2-dimensional array structure of Sidelnikov sequences of period \(q^{d}-1\). In: Proceedings of IWSDA’13, pp. 20–23 (2013)
21.
go back to reference Kim, Y., Kim, D., Song, H.: New \(M\)-ary sequence families with low correlation from the array structure of Sidelnikov sequences. IEEE Trans. Inf. Theory 61(1), 655–670 (2015)MathSciNetCrossRef Kim, Y., Kim, D., Song, H.: New \(M\)-ary sequence families with low correlation from the array structure of Sidelnikov sequences. IEEE Trans. Inf. Theory 61(1), 655–670 (2015)MathSciNetCrossRef
22.
go back to reference Kim, Y., Song, H.: Cross correlation of Sidel’nikov sequences and their constant multiples. IEEE Trans. Inf. Theory 53(3), 1220–1224 (2007)CrossRef Kim, Y., Song, H.: Cross correlation of Sidel’nikov sequences and their constant multiples. IEEE Trans. Inf. Theory 53(3), 1220–1224 (2007)CrossRef
23.
go back to reference Kyureghyan, G.M., Pott, A.: On the linear complexity of the Sidelnikov–Lempel–Cohn–Eastman sequences. Des. Codes Cryptogr. 29(1–3), 149–164 (2003)MathSciNetCrossRef Kyureghyan, G.M., Pott, A.: On the linear complexity of the Sidelnikov–Lempel–Cohn–Eastman sequences. Des. Codes Cryptogr. 29(1–3), 149–164 (2003)MathSciNetCrossRef
24.
go back to reference Lempel, A., Cohn, M., Eastman, W.L.: A class of balanced binary sequences with optimal autocorrelation properties. IEEE Trans. Inf. Theory IT–23(1), 38–42 (1977)MathSciNetCrossRef Lempel, A., Cohn, M., Eastman, W.L.: A class of balanced binary sequences with optimal autocorrelation properties. IEEE Trans. Inf. Theory IT–23(1), 38–42 (1977)MathSciNetCrossRef
25.
go back to reference Meidl, W., Winterhof, A.: Some notes on the linear complexity of Sidelnikov–Lempel–Cohn–Eastman sequences. Des. Codes Cryptogr. 38(2), 159–178 (2006)MathSciNetCrossRef Meidl, W., Winterhof, A.: Some notes on the linear complexity of Sidelnikov–Lempel–Cohn–Eastman sequences. Des. Codes Cryptogr. 38(2), 159–178 (2006)MathSciNetCrossRef
26.
go back to reference Sidel’nikov, V.M.: Some \(k\)-valued pseudo-random sequences and nearly equidistant codes. Probl. Inf. Transm. 5(1), 12–16 (1969)MathSciNet Sidel’nikov, V.M.: Some \(k\)-valued pseudo-random sequences and nearly equidistant codes. Probl. Inf. Transm. 5(1), 12–16 (1969)MathSciNet
27.
go back to reference Wanders, H.E.: On the significance of Golomb’s randomness postulates in cryptography. Philips J. Res. 43(2), 185–222 (1988)MathSciNet Wanders, H.E.: On the significance of Golomb’s randomness postulates in cryptography. Philips J. Res. 43(2), 185–222 (1988)MathSciNet
28.
go back to reference Winterhof, A., Xiao, Z.: Binary sequences derived from differences of consecutive primitive roots. IEEE Trans. Inf. Theory 67(8), 5334–5338 (2021)MathSciNetCrossRef Winterhof, A., Xiao, Z.: Binary sequences derived from differences of consecutive primitive roots. IEEE Trans. Inf. Theory 67(8), 5334–5338 (2021)MathSciNetCrossRef
29.
go back to reference Yu, N.Y., Gong, G.: New construction of \(M\)-ary sequence families with low correlation from the structure of Sidelnikov sequences. IEEE Trans. Inf. Theory 56(8), 4061–4070 (2010)MathSciNetCrossRef Yu, N.Y., Gong, G.: New construction of \(M\)-ary sequence families with low correlation from the structure of Sidelnikov sequences. IEEE Trans. Inf. Theory 56(8), 4061–4070 (2010)MathSciNetCrossRef
30.
go back to reference Yu, N.Y., Gong, G.: Multiplicative characters, the Weil bound, and polyphase sequence families with low correlation. IEEE Trans. Inf. Theory 56(12), 6376–6387 (2010)MathSciNetCrossRef Yu, N.Y., Gong, G.: Multiplicative characters, the Weil bound, and polyphase sequence families with low correlation. IEEE Trans. Inf. Theory 56(12), 6376–6387 (2010)MathSciNetCrossRef
Metadata
Title
Balance, pattern distribution and linear complexity of M-ary sequences from Sidel’nikov sequences
Authors
Huaning Liu
Yixin Ren
Publication date
07-09-2022
Publisher
Springer Berlin Heidelberg
Published in
Applicable Algebra in Engineering, Communication and Computing / Issue 5/2024
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-022-00580-5

Premium Partner