Advertisement

Special Distribution of the Shortest Linear Recurring Sequences in Z /(p) Field

  • Qian Yin
  • Yunlun Luo
  • Ping Guo
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3802)

Abstract

In this paper, the distribution of the shortest linear recurring sequences in Z /(p) is studied. It is found that the shortest linear recurrent length is always equal to n / 2 when n is even and is always equal to n / 2+1 when n is odd for any sequence whose length is n. In other words, the shortest linear recurring length is always equal to the half of the length of the given sequence. The probability of finding the distribution of the shortest linear recurring length of two sequences in Z / (p) field is also given.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Meidl, W.: On the Stability of 2n-Periodic Binary Sequences. IEEE Trans. Inform Theory, IT-51(3), 1151–1155 (2005)CrossRefMathSciNetGoogle Scholar
  2. 2.
    Reeds, J.A., Sloane, N.J.A.: Shift-register synthesis (modulo m). SIAM Journal on Computing 14(3), 505–513 (1985)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Dingfeng, Y., Zongduo, D.: Periodic sequence linear order of complexity under two marks replacing. In: Fourth session of Chinese cryptology academic conference collection (1996) (in Chinese)Google Scholar
  4. 4.
    Yujie, Z., Jinjun, Z.: The relationship between two kinds of sequences syntheses algorithm over ring Z/(m). In: Fifth session of Chinese cryptology academic conference collection (1998) (in Chinese)Google Scholar
  5. 5.
    Liying, G., Yuefei, Z.: The shortest linear recurrence of two sequences. Journal of information engineering university 2(1), 17–22 (2001) (in Chinese)Google Scholar
  6. 6.
    Guiliang, F., Tzeng, K.K.A.: Generalization of the Berlekamp-Massey algorithm for multi-sequence shift-register synthesis with applications to decoding cyclic codes. IEEE Trans. Inform. Theory 37(5), 1274–1287 (1991)CrossRefMathSciNetGoogle Scholar
  7. 7.
    Guiliang, F., Tzeng, K.K.A.: Generalized Euclidean algorithm for multi-sequence shift-register synthesis. IEEE Trans. Inform. Theory 35(3), 584–594 (1989)CrossRefMathSciNetGoogle Scholar
  8. 8.
    Jinjun, Z., Wenfeng, Q., Yujie, Z.: Gröbner base extension and Multi-sequences comprehensive algorithm over Z/(m). Science in China, 113–120 (1995) (in Chinese)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Qian Yin
    • 1
  • Yunlun Luo
    • 1
  • Ping Guo
    • 1
  1. 1.Department of Computer Science, College of Information Science and TechnologyBeijing Normal UniversityBeijingChina

Personalised recommendations