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

DOI:
https://doi.org/10.1090/S0025-5718-08-02075-9

Published electronically:
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.

**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 ,''*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 ,''*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 ,''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 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 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 ,''*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 ,''*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.)

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11B50,
94A55

Retrieve articles in all journals with MSC (2000): 11B50, 94A55

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

DOI:
https://doi.org/10.1090/S0025-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

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.

Article copyright:
© Copyright 2008
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.