Skip to main content
Log in

Injective maps on primitive sequences over Z/(p e)

  • Published:
Applied Mathematics-A Journal of Chinese Universities Aims and scope Submit manuscript

Abstract

Let Z/(p e) be the integer residue ring modulo p e with p an odd prime and integer e ≥ 3. For a sequence \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} \) over Z/(p e), there is a unique p-adic decomposition \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _0 + \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _1 \cdot p + \cdots + \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _{e - 1} \cdot p^{e - 1} \), where each \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _i \) can be regarded as a sequence over Z/(p), 0 ≤ ie − 1. Let f(x) be a primitive polynomial over Z/(p e) and G′(f(x), p e) the set of all primitive sequences generated by f(x) over Z/(p e). For μ(x) ∈ Z/(p)[x] with deg(μ(x)) ≥ 2 and ged(1 + deg(μ(x)), p − 1) = 1, set

$$\varphi _{e - 1} (x_0 ,x_1 , \cdots ,x_{e - 1} ) = x_{e - 1} \cdot \left[ {\mu (x_{e - 2} ) + \eta _{e - 3} (x_0 ,x_1 , \cdots ,x_{e - 3} )} \right] + \eta _{e - 2} (x_0 ,x_1 , \cdots ,x_{e - 2} ),$$

which is a function of e variables over Z/(p). Then the compressing map

$$\varphi _{e - 1} :G'(f(x),p^e ) \to (Z/(p))^\infty ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} \mapsto \varphi _{e - 1} (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _0 ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _1 , \cdots \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _{e - 1} )$$

is injective. That is, for \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} \in G'(f(x),p^e ),\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} = \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} \) and only if \(\varphi _{e - 1} (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _0 ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _1 , \cdots \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _{e - 1} ) = \varphi _{e - 1} (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} _0 ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} _1 , \cdots ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} _{e - 1} )\). As for the case of e = 2, similar result is also given. Furthermore, if functions ε e − 1 and ψ e − 1 over Z/(p) are both of the above form and satisfy

$$\varphi _{e - 1} (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _0 ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _1 , \cdots \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} _{e - 1} ) = \psi _{e - 1} (\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} _0 ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} _1 , \cdots ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} _{e - 1} )$$

for \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} \in G'(f(x),p^e )\), the relations between \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{a} \) and \(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{b} \), ε e − 1 and ψ e − 1 are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Dai Z D. Binary sequences derived from ML-sequences over rings I: periods and minimal polynomials, J Cryptology, 1992, 5(4): 193–207.

    Article  MATH  MathSciNet  Google Scholar 

  2. Huang M Q, Dai Z D. Projective maps of linear recurring sequences with maximal p-adic periods, Fibonacci Quart, 1992, 30(2): 139–143.

    MATH  MathSciNet  Google Scholar 

  3. Kuzmin A S, Nechaev A A. Linear recurring sequences over Galois ring, Russian Mathematical Surveys, 1993, 48(1): 171–172.

    Article  MathSciNet  Google Scholar 

  4. Huang M Q. Analysis and cryptological evaluation of primitive sequences over an integer residue ring, Ph.D. dissertation, Beijing: Graduate School of USTC, 1988.

    Google Scholar 

  5. Qi W F, Zhou J J. Classes of injective maps on primitive sequences over Z/(2d), Prog Nat Sci, 1999, 9(3): 209–215.

    Google Scholar 

  6. Qi W F. Compressing maps of primitive sequences over Z/(2e) and analysis of their derived sequences, Ph.D. dissertation, Zhengzhou: Zhengzhou Inform Eng Univ, China, 1997.

    Google Scholar 

  7. Qi W F, Yang J H, Zhou J J. ML-sequences over rings Z/(2e), In: Advances in Cryptology-ASIACRYPT’98, Lecture Notes in Computer Science 1514. Berlin, Heidelberg: Springer-Verlag, 1998, 315–325.

    Chapter  Google Scholar 

  8. Zhu X Y, Qi W F. Compressing mappings on primitive sequences over Z/(2e) and its Galois extension, Finite Fields and Their Applications, 2002, 8(4): 570–588.

    MATH  MathSciNet  Google Scholar 

  9. Dai Z D, Beth T, Gollman D. Lower bounds for the linear complexity of sequences over residue ring, In: Advances in Cryptology-EUROCRYPT’90, Lecture Notes in Computer Science 473, Berlin, Heidelberg: Springer, 1991, 189–195.

    Google Scholar 

  10. Kuzmin A S. Lower estimates for the ranks of coordinate sequences of linear recurrent sequences over primary residue rings of integers, Russian Mathematical Surveys, 1993, 48(3): 203–204.

    Article  MathSciNet  Google Scholar 

  11. Qi W F, Zhou J J. The distribution of 0 and 1 in the highest level of primitive sequences over Z/(2e), Science in China Ser A, 1997, 27(4): 311–316.

    Google Scholar 

  12. Qi W F, Zhou J J. The distribution of 0 and 1 in the highest level of primitive sequences over Z/(2e) (II), Chinese Science Bulletin, 1997, 42(18): 1938–1940.

    MathSciNet  Google Scholar 

  13. Fan S Q, Han W B. The distribution of 0 and 1 in the highest level of primitive sequences over Z/(2e), Science in China Ser A, 2002, 32(11): 983–990.

    Google Scholar 

  14. Zhu X Y, Qi W F. Uniqueness of the distribution of zeros of primitive level sequences over Z/(p e), Finite Fields and Their Applications, 2005, 11(1): 30–44.

    Article  MATH  MathSciNet  Google Scholar 

  15. Zhu X Y, Qi W F. Compressing mappings on primitive sequences over Z/(p e), IEEE Transactions on Information Theory, 2004, 50(10): 2442–2448.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

Supported by the National Natural Science Foundation of China (60673081) and 863 Program (2006AA01Z417).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sun, Z., Qi, W. Injective maps on primitive sequences over Z/(p e). Appl. Math.- J. Chin. Univ. 22, 469–477 (2007). https://doi.org/10.1007/s11766-007-0413-0

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11766-007-0413-0

MR Subject Classification

Keywords

Navigation