On the distinctness of modular reductions of maximal length sequences modulo odd prime powers
HTML articles powered by AMS MathViewer
- by Xuan-Yong Zhu and Wen-Feng Qi PDF
- Math. Comp. 77 (2008), 1623-1637 Request permission
Abstract:
We discuss the distinctness problem of the reductions modulo $M$ of maximal length sequences modulo powers of an odd prime $p$, where the integer $M$ has a prime factor different from $p$. For any two different maximal length sequences generated by the same polynomial, we prove that their reductions modulo $M$ are distinct. In other words, the reduction modulo $M$ of a maximal length sequence is proved to contain all the information of the original sequence.References
- 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, DOI 10.1007/BF02451115
- Zong Duo Dai and Min Qiang Huang, A criterion for primitiveness of polynomials over $\textbf {Z}/(2^d)$, Chinese Sci. Bull. 36 (1991), no. 11, 892–895. MR 1138295
- 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, DOI 10.1109/18.605605
- 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, DOI 10.1109/18.825843
- Min Qiang Huang and Zong Duo Dai, Projective maps of linear recurring sequences with maximal $p$-adic periods, Fibonacci Quart. 30 (1992), no. 2, 139–143. MR 1162415
- Min Qiang Huang, Maximal period polynomials over $\mathbf Z/(p^d)$, Sci. China Ser. A 35 (1992), no. 3, 270–275. MR 1183712
- 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.
- 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, DOI 10.1007/s001459900024
- 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, DOI 10.1007/BF02362772
- 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.
- 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
- Bernard R. McDonald, Finite rings with identity, Pure and Applied Mathematics, Vol. 28, Marcel Dekker, Inc., New York, 1974. MR 0354768
- 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.)
- 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.
- 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.)
- Qi Wenfeng and Zhu Xuanyong, Compressing mappings on primitive sequences over $\mathbf Z/(2^e)$ and its Galois extension, Finite Fields Appl. 8 (2002), no. 4, 570–588. MR 1933627
- Wenfeng Qi and Hong Xu, Partial period distribution of FCSR sequences, IEEE Trans. Inform. Theory 49 (2003), no. 3, 761–765. MR 1967204, DOI 10.1109/TIT.2002.808130
- 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, DOI 10.1109/18.825844
- Morgan Ward, The arithmetical theory of linear recurring series, Trans. Amer. Math. Soc. 35 (1933), no. 3, 600–628. MR 1501705, DOI 10.1090/S0002-9947-1933-1501705-4
- Xuan-Yong Zhu and Wen-Feng Qi, Uniqueness of the distribution of zeroes of primitive level sequences over $\mathbf Z/(p^e)$, Finite Fields Appl. 11 (2005), no. 1, 30–44. MR 2111896, DOI 10.1016/j.ffa.2004.04.001
- Xuan Yong Zhu and Wen Feng Qi, Compression mappings on primitive sequences over $Z/(p^e)$, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2442–2448. MR 2097062, DOI 10.1109/TIT.2004.834791
- 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.)
Additional Information
- Xuan-Yong Zhu
- Affiliation: China National Digital Switching System Engineering and Technological R&D Center (NDSC), P.O. Box 1001-783, Zhengzhou, 450002, People’s Republic of China
- Email: xuanyong.zhu@263.net or zxy@mail.ndsc.com.cn
- Wen-Feng Qi
- Affiliation: Department of Applied Mathematics, Zhengzhou Information Engineering University, P.O. Box 1001-745, Zhengzhou, 450002, People’s Republic of China
- Email: wenfeng.qi@263.net
- Received by editor(s): August 9, 2004
- Received by editor(s) in revised form: May 24, 2007
- Published electronically: January 31, 2008
- Additional Notes: This work was supported by the National 863 Plan of China (Grant 2006AA01Z417) and the National Natural Science Foundation of China (Grant 60673081)
This paper is in final form and no version of it will be submitted for publication elsewhere. - © Copyright 2008
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 77 (2008), 1623-1637
- MSC (2000): Primary 11B50, 94A55
- DOI: https://doi.org/10.1090/S0025-5718-08-02075-9
- MathSciNet review: 2398784