Skip to main content
SpringerLink
Log in

About computation of the linear complexity of generalized cyclotomic sequences with period p n+1

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

We propose a computation method for linear complexity of series of generalized cyclotomic sequences with period p n+1. This method is based on using the polynomial of the classic cyclotomic sequences of period p. We found the linear complexity of generalized cyclotomic sequences corresponding to the classes of biquadratic residues and Hall sequences.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ding C., Helleseth T.: New generalized cyclotomy and its applications. Finite Fields Appl. 4, 140–166 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ireland K., Rosen M.: A Classical Introduction to Modern Number Theory. Springer, Berlin (1982)

    MATH  Google Scholar 

  3. Ding C.: Linear complexity of some generalized cyclotomic sequences. Int. J. Algebra Comput. 8(4), 431–442 (1998)

    Article  MATH  Google Scholar 

  4. Park Y.H., Hong D., Chun E.: On the linear complexity of some generalized cyclotomic sequences. Int. J. Algebra Comput. 14(4), 431–439 (2004)

    Article  MATH  Google Scholar 

  5. Bai E., Liu X.: Some notes on prime-square sequences. J. Comput. Sci. Technol. 22(3), 481–486 (2007)

    Article  MathSciNet  Google Scholar 

  6. Yan T., Sun R., Xiao G.: Autocorrelation and linear complexity of the new generalized cyclotomic sequences. IEICE Trans. Fund. Electron. E E90A, 857–864 (2007)

    Article  Google Scholar 

  7. Kim Y.-J., Jin S.-Y., Song H.-Y.: Linear complexity and autocorrelation of prime cube sequences. In: Lecture Notes in Computer Science, vol. 4851, pp. 188–197. Springer, Berlin (2007).

  8. Kim Y.J., Song H.Y.: Linear complexity of prime n-square sequences. In: IEEE International Symposium on Information Theory, Toronto, Canada, pp. 2405–2408 (2008).

  9. Yan T., Li S., Xiao G.: On the linear complexity of generalized cyclotomic sequences with the period p m. Appl. Math. Lett. 21, 187–193 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  10. Hall M.: Combinatorial Theory. Wiley, New York (1975)

    Google Scholar 

  11. Cusick T.W., Ding C., Renvall A.: Stream Ciphers and Number Theory. North-Holland Publishing Co., Amsterdam (1998)

    MATH  Google Scholar 

  12. Kim J.H., Song H.Y.: On the linear complexity of Hall’s sextic residue sequences. IEEE Trans. Inform. Theory 47, 2094–2096 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  13. Lidl R., Neid H.: Finite Fields (Encyclopedia of Mathematics and Its Applications), vol. 20. Reading, MA: Addison-Wesley (1983).

  14. Ding C., Helleseth T., Shan W.: On the linear complexity of Legendre sequences. IEEE Trans. Inform. Theory 44, 1276–1278 (1998)

    Article  MathSciNet  Google Scholar 

  15. Edemskii V.A.: On the linear complexity of binary sequences on the basis of biquadratic and sextic residue classes. Discret. Math. Appl. 20(1), 75–84 (2010) (Diskretn. Mat. 22(1), 74–82 (2010)).

  16. Edemskiy V.A.: Linear complexity of ternary sequences formed on the basis of power residue classes. Probl. Inform. Transm. 44(4), 287–294 (2008) (Probl. Peredachi Inform. 44(4), 3–11 (2008)).

  17. Ding C., Helleseth T., Lam K.Y.: Several classes of binary sequences with three-level autocorrelation. IEEE Trans. Inform. Theory 45, 2606–2612 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  18. Dai Z.D., Gong G., Song H.Y.: Trace representation and linear complexity of binary e-th residue sequences. In: Proceedings of International Workshop on Coding and Cryptography (WCC2003), 24–28 March 2003, Versailles, France, pp. 121–133.

Download references

Author information

Authors and Affiliations

  1. Novgorod State University, Str. B. St. Petersburgskaya, 41, 173003, Veliky Novgorod, Russia

    Vladimir Edemskiy

Authors
  1. Vladimir Edemskiy
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vladimir Edemskiy.

Additional information

Communicated by T. Helleseth.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Edemskiy, V. About computation of the linear complexity of generalized cyclotomic sequences with period p n+1 . Des. Codes Cryptogr. 61, 251–260 (2011). https://doi.org/10.1007/s10623-010-9474-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-010-9474-9

Keywords

Mathematics Subject Classification (2000)

Search

Navigation