Mathematics of Computation

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

On the distinctness of modular reductions of maximal length sequences modulo odd prime powers

Authors: Xuan-Yong Zhu and Wen-Feng Qi
Journal: Math. Comp. 77 (2008), 1623-1637
MSC (2000): Primary 11B50, 94A55
Posted: January 31, 2008
MathSciNet review: 2398784
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We discuss the distinctness problem of the reductions modulo of maximal length sequences modulo powers of an odd prime , where the integer has a prime factor different from . For any two different maximal length sequences generated by the same polynomial, we prove that their reductions modulo are distinct. In other words, the reduction modulo of a maximal length sequence is proved to contain all the information of the original sequence.

References

1. Zong Duo Dai, Binary sequences derived from ML-sequences over rings. I. Periods and minimal polynomials, J. Cryptology 5 (1992), no. 3, 193–207. MR 1193387 (93g:68030), http://dx.doi.org/10.1007/BF02451115
2. Zong Duo Dai and Min Qiang Huang, A criterion for primitiveness of polynomials over 𝑍/(2^{𝑑}), Chinese Sci. Bull. 36 (1991), no. 11, 892–895. MR 1138295 (93d:11126)
3. Mark Goresky and Andrew Klapper, Arithmetic crosscorrelations of feedback with carry shift register sequences, IEEE Trans. Inform. Theory 43 (1997), no. 4, 1342–1345. MR 1454969 (98j:94010), http://dx.doi.org/10.1109/18.605605
4. Mark Goresky, Andrew M. Klapper, and Lawrence Washington, Fourier transforms and the 2-adic span of periodic binary sequences, IEEE Trans. Inform. Theory 46 (2000), no. 2, 687–691. MR 1748998 (2001k:94041), http://dx.doi.org/10.1109/18.825843
5. Min Qiang Huang and Zong Duo Dai, Projective maps of linear recurring sequences with maximal 𝑝-adic periods, Fibonacci Quart. 30 (1992), no. 2, 139–143. MR 1162415 (93b:11012)
6. Min Qiang Huang, Maximal period polynomials over 𝐙/(𝐩^{𝐝}), Sci. China Ser. A 35 (1992), no. 3, 270–275. MR 1183712 (93e:11148)
7. M.Q. Huang, ``Analysis and cryptologic evaluation of primitive sequences over an integer residue ring,''Ph.D. dissertation, Graduate School of USTC, Academia Sinica, Beijing, China, 1988.
8. Andrew Klapper and Mark Goresky, Feedback shift registers, 2-adic span, and combiners with memory, J. Cryptology 10 (1997), no. 2, 111–147. MR 1447843 (98f:94012), http://dx.doi.org/10.1007/s001459900024
9. V. L. Kurakin, A. S. Kuzmin, A. V. Mikhalev, and A. A. Nechaev, Linear recurring sequences over rings and modules, J. Math. Sci. 76 (1995), no. 6, 2793–2915. Algebra, 2. MR 1365809 (97a:11201), http://dx.doi.org/10.1007/BF02362772
10. A.S. Kuzmin and A.A. Nechaev, ``Linear recurring sequences over Galois rings,'' Algebra and Logic, vol. 34, no. 2, pp. 87-100, 1995; translation from Algebra Logika, vol. 34, no. 2, pp. 169-189, 1995.
11. Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963 (86c:11106)
12. Bernard R. McDonald, Finite rings with identity, Marcel Dekker Inc., New York, 1974. Pure and Applied Mathematics, Vol. 28. MR 0354768 (50 #7245)
13. A.A. Nechaev, ``Linear recurring sequences over commutative rings,''Diskr. Math., vol. 3, no. 4, pp. 105-127, 1991. (English translation: Diskrete Math. and Appl., vol. 2, no. 6, pp. 659-683, 1992.)
14. W.F. Qi, J.H. Yang, and J.J. Zhou, `` ML-sequences over rings $\mathbb{Z}/(2^{e})$ ,''in Advances in Cryptology--ASIACRYPT'98 (Lecture Notes in Computer Science). Berlin/Heidelberg, Germany: Springer-Verlag, 1998, vol. 1514, pp. 315-325.
15. W.F. Qi, ``Compressing maps of primitive sequences over $\mathbb{Z}/(2^{e})$ and analysis of their derivative sequences,''Ph.D. Dissertation, Zhengzhou Inform. Eng. Univ., Zhengzhou, China, 1997. Higher Education Press, Beijing, December 2001. (In Chinese.)
16. Qi Wenfeng and Zhu Xuanyong, Compressing mappings on primitive sequences over 𝐙/(2^{𝐞}) and its Galois extension, Finite Fields Appl. 8 (2002), no. 4, 570–588. MR 1933627 (2004f:11015)
17. Wenfeng Qi and Hong Xu, Partial period distribution of FCSR sequences, IEEE Trans. Inform. Theory 49 (2003), no. 3, 761–765. MR 1967204 (2004c:94079), http://dx.doi.org/10.1109/TIT.2002.808130
18. Changho Seo, Sangjin Lee, Yeoulouk Sung, Keunhee Han, and Sangchoon Kim, A lower bound on the linear span of an FCSR, IEEE Trans. Inform. Theory 46 (2000), no. 2, 691–693. MR 1748999 (2000m:94017), http://dx.doi.org/10.1109/18.825844
19. Morgan Ward, The arithmetical theory of linear recurring series, Trans. Amer. Math. Soc. 35 (1933), no. 3, 600–628. MR 1501705, http://dx.doi.org/10.1090/S0002-9947-1933-1501705-4
20. Xuan-Yong Zhu and Wen-Feng Qi, Uniqueness of the distribution of zeroes of primitive level sequences over 𝐙/(𝐩^{𝐞}), Finite Fields Appl. 11 (2005), no. 1, 30–44. MR 2111896 (2005i:11023), http://dx.doi.org/10.1016/j.ffa.2004.04.001
21. Xuan Yong Zhu and Wen Feng Qi, Compression mappings on primitive sequences over 𝑍/(𝑝^{𝑒}), IEEE Trans. Inform. Theory 50 (2004), no. 10, 2442–2448. MR 2097062, http://dx.doi.org/10.1109/TIT.2004.834791
22. X.Y. Zhu, ``Some results on injective mappings of primitive sequences modulo prime powers,'' Ph.D. Dissertation, Zhengzhou Inform. Eng. Univ., Zhengzhou, China, December 2004. (In Chinese.)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|