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 ≤ i ≤ e − 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
which is a function of e variables over Z/(p). Then the compressing map
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
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.
Similar content being viewed by others
References
Dai Z D. Binary sequences derived from ML-sequences over rings I: periods and minimal polynomials, J Cryptology, 1992, 5(4): 193–207.
Huang M Q, Dai Z D. Projective maps of linear recurring sequences with maximal p-adic periods, Fibonacci Quart, 1992, 30(2): 139–143.
Kuzmin A S, Nechaev A A. Linear recurring sequences over Galois ring, Russian Mathematical Surveys, 1993, 48(1): 171–172.
Huang M Q. Analysis and cryptological evaluation of primitive sequences over an integer residue ring, Ph.D. dissertation, Beijing: Graduate School of USTC, 1988.
Qi W F, Zhou J J. Classes of injective maps on primitive sequences over Z/(2d), Prog Nat Sci, 1999, 9(3): 209–215.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Author information
Authors and Affiliations
Additional information
Supported by the National Natural Science Foundation of China (60673081) and 863 Program (2006AA01Z417).
Rights 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
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11766-007-0413-0