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

Zhu, Xuan-Yong; Qi, Wen-Feng

doi:10.1090/S0025-5718-08-02075-9

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.)