Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ 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 [Enhancements On Off] (What's this?)

  • 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 $ p$-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.)

Similar Articles

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.

American Mathematical Society