Mathematics of Computation

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

Author(s): Xuan-Yong Zhu; Wen-Feng Qi.
Journal: Math. Comp. 77 (2008), 1623-1637.
MSC (2000): Primary 11B50, 94A55
Posted: January 31, 2008
Retrieve article in: PDF DVI PostScript

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.

1.: Z.D. Dai, ``Binary sequences derived from ML-sequences over rings I: periods and minimal polynomials,''J. Cryptology, vol. 5, no. 4, pp. 193-207, 1992. MR 1193387 (93g:68030)
2.: Z.D. Dai and M.Q. Huang, ``A criterion for primitiveness of polynomial over $\mathbb{Z}/(2^{d})$ ,'' Chinese Sci. Bull., vol. 36, pp. 892-895, 1991. MR 1138295 (93d:11126)
3.: M. Goresky and A. Klapper, ``Arithmetic crosscorrelation of feedback with carry shift register sequences,''IEEE Trans. Inform. Theory, vol. 43, no. 4, pp. 1342-1345, 1997. MR 1454969 (98j:94010)
4.: M. Goresky and A. Klapper, ``Fourier transforms and the 2-adic span of periodic binary sequences,''IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 687-691, 2000. MR 1748998 (2001k:94041)
5.: M.Q. Huang and Z.D. Dai, ``Projective maps of linear recurring sequences with maximal -adic periods,''Fibonacci Quart., vol. 30, no. 2, pp. 139-143, 1992. MR 1162415 (93b:11012)
6.: M.Q. Huang, ``Maximal period polynomials over $\mathbb{Z}/(p^{d})$ ,''Sci. in China, Ser. A , vol. 35, pp. 271-275, 1992. 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.: A. Klapper and M. Goresky, ``Feedback shift registers, 2-adic span, and combiners with memory,'' J. Cryptology, vol. 10, pp. 111-147, 1997. MR 1447843 (98f:94012)
9.: V.L. Kurakin, A.S. Kuzmin, A.V. Mikhalev, and A.A. Nechaev, ``Linear recurring sequences over rings and modules,''J. Math. Sci., vol. 76, no. 6, pp. 2793-2915, 1995. MR 1365809 (97a:11201)
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.: R. Lidl and H. Niederreiter, Finite fields, in Encyclopedia of Mathematics and its Applications. Cambridge, U.K.: Cambridge Univ. Press, 1983. vol. 20. MR 746963 (86c:11106)
12.: B.R. McDonald, Finite Rings with Identity, Marcel Dekker, New York, 1974. 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.: W.F. Qi and X.Y. Zhu, ``Compressing mappings on primitive sequences over $\mathbb{Z}/(2^{e})$ and its Galois extension,''Finite Fields Appl., vol. 8, no. 4, pp. 570-588, Oct. 2002. MR 1933627 (2004f:11015)
17.: W.F. Qi and H. Xu, ``Partial period distribution of FCSR sequences,''IEEE Trans. Inform. Theory, vol. 49, no. 3, pp. 761-765, 2003. MR 1967204 (2004c:94079)
18.: C. Seo, S. LEE, Y. Sung, K. Han, and S. Kim, ``A lower bound on the linear span of an FCSR,''IEEE Trans. Inform. Theory, vol. 46, no. 2, pp. 691-693, 2000. MR 1748999 (2000m:94017)
19.: M. Ward, ``The arithmetical theory of linear recurring series,''Trans. Amer. Math. Soc. , vol. 35, pp. 600-628, July 1933. MR 1501705
20.: X.Y. Zhu and W.F. Qi, ``Uniqueness of the distribution of zeroes of primitive level sequences over $\mathbb{Z}/(p^{e})$ ,''Finite Fields Appl., vol. 11, no. 1, pp. 30-44, Jan. 2005. MR 2111896 (2005i:11023)
21.: X.Y. Zhu and W.F. Qi, ``Compression mappings on primitive sequences over $\mathbb{Z}/(p^{e})$ ,'' IEEE Trans. Inform. Theory, vol. 50, no. 10, pp. 2442-2448, Oct. 2004. MR 2097062
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.)

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

DOI: 10.1090/S0025-5718-08-02075-9
PII: S 0025-5718(08)02075-9
Keywords: Integer residue ring, linear recurring sequence, primitive polynomial, primitive sequence, modular reduction
Received by editor(s): August 9, 2004
Received by editor(s) in revised form: May 24, 2007
Posted: 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 of article: Copyright 2008, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

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

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS