Injectivity of compressing maps on the set of primitive sequences modulo square-free odd integers

详细信息    查看全文

• 作者：Zhi Hu ; Lin Wang
• 关键词：Stream cipher ; Residue ring ; Compressing map ; Primitive sequence ; Modular function ; 94A55 ; 11B50
• 刊名：Cryptography and Communications
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：7
• 期：4
• 页码：347-361
• 全文大小：258 KB
• 参考文献：1.Bugeaud, Y., Corvaja, P., Zannier, U.: An upper bound for the G.C.D. of a n ? and b n ?. Math. Z. 243, 79-4 (2003)MathSciNet View Article
  2.Chen, H.-J., Qi, W.-F.: On the distinctness of maximal length sequences over Z/(p q) modulo 2. Finite Fields Appl. 15(1), 23-9 (2009)MathSciNet View Article
  3.Dai, Z. D., Beth, T., Gollman, D.: Lower bounds for the linear complexity of sequences over residue ring. In: Advances in Cryptology-EUROCRYPT-0, pp 189-95. Springer, Berlin (1991). LNCS 473
  4.Fan, S.-Q., Han, W.-B.: Random properties of the highest level sequences of primitive sequences over \(Z_{2^{e}}\) . IEEE Trans. Inf. Theory 49(6), 1553-557 (2003)MathSciNet View Article
  5.Fuchs, C.: An upper bound for the G.C.D. of two linear recurring sequences. Mathematica Slovaca 53(1), 21-2 (2003) http://?dml.?cz/?dmlcz/-30345 MathSciNet
  6.Huang, M.-Q.: Analysis and cryptologic evaluation of primitive sequences over an integer residue ring, Ph.D. dissertation, Graduate School of USTC. Academia Sinica, Beijing (1988). (in Chinese)
  7.Huang, M.-Q., Dai, Z.-D.: Projective maps of linear recurring sequences with maximal p-adic periods. Fibonacci Quart. 30(2), 139-43 (1992)MathSciNet
  8.Korobov, N. M.: Exponential sums and their applications. Kluwer, Dordrecht (1992)View Article
  9.Kuzmin, A. S.: Lower estimates for the ranks of coordinate sequences of linear recurrent sequences over primary residue rings of integers. Russian Math. Surv. 48(3), 203-04 (1993)MathSciNet View Article
  10.Kurakin, V. L., Kuzmin, A. S., Mikhalev, A. V., Nechaev, A. A.: Linear recurring sequences over rings and modules. J. Math. Sci. 76(6), 2793-915 (1995)MathSciNet View Article
  11.Kuzmin, A. S., Nechaev, A. A.: Linear recurring sequences over Galois ring, Russian. Math. Surv. 48(1), 171-72 (1993)MathSciNet View Article
  12.Kuzmin, A. S., Nechaev, A. A.: Linear recurring sequences over Galois rings. Algebra Logic 34(2), 87-00 (1995)MathSciNet View Article
  13.Lidl, R., Niederreiter, H.: Finite fields, in Encyclopedia of Mathematics and its Applications. Addison-Wesley Publishing Company, Inc, USA (1983)
  14.Nechaev, A. A.: Linear recurring sequences over commutative rings. Discrete Math. 3(4), 107-21 (1991)
  15.Qi, W.-F.: Compressing maps of primitive sequences over Z/(2 e ) and analysis of their derivative sequences. Higher Education Press, Beijing (2001). (in Chinese)
  16.Qi, W.-F., Yang, J.-H., Zhou, J.-J.: ML-sequences over rings Z/(2 e ). In: Advances in Cryptology–ASIACRYPT-8, pp 315-26. Springer-Verlag, Berlin (1998). LNCS 1514
  17.Qi, W.-F., Zhou, J.-J.: The distribution of 0 and 1 in the highest level sequence of primitive sequences over \(\mathbb {Z}/(2^{e})\) . Sci. China, ser.A 27(4), 311-16 (1997). (in Chinese)MathSciNet
  18.Qi, W.-F., Zhou, J.-J.: The distribution of 0 and 1 in the highest level sequence of primitive sequences over Z/(2 e ) (II). Chinese Sci. Bull. 42(18), 1938-940 (1997). (in Chinese)MathSciNet
  19.Solé, P., Zinoviev, D.: The most significant bit of maximum-length sequences over \(\mathbb {Z}_{2^{l}}\) : autocorrelation and imbalance. IEEE Trans. Inf. Theory 50(8), 1844-846 (2004)View Article
  20.Sun, Z.-H., Qi, W.-F.: Injective maps on primitive sequences over Z/(p e ). Appl. Math. J. Chinese Univ. Ser.B 22(4), 469-77 (2007)MathSciNet View Article
  21.Tian, T., Qi, W.-F.: Injectivity of compressing maps on primitive sequences over \(\mathbb {Z}/(p^{e})\) . IEEE Trans. Inf. Theory 53(8), 2960-966 (2007)MathSciNet View Article
  22.Ward, M.: The arithmetical theory of linear recurring series. Trans. Amer. Math. Soc. 35, 600-28 (1933)MathSciNet View Article
  23.Zeng, K.-C., Dai, Z.-D., Huang, M.-Q.: Injectiveness of mappings from ring sequences to their sequences of significant bits, Symposium on Problems of Cryptology, State Key Laboratory of Information Security, Beijing, China, pp 132-41 (1995)
  24.Zheng, Q.-X., Qi, W.-F.: A new result on the distinctness of primitive sequences over \(\mathbb {Z}/(pq)\) modulo 2. Finite Fields Appl. 17(3), 254-74 (2011)MathSciNet View Article
  25.Zheng, Q.-X., Qi, W.-F., Tian, T.: On the distinctness of modular reductions of primitive sequences over \(\mathbb {Z}/(2^{32}-1)\) , Des. Codes Cryptogr. to be published [Online]. doi:10.-007/?s10623-012-9698-y
  26.Zheng, Q.-X., Qi, W.-F., Tian, T.: On the distinctness of modular reductions of primitive sequences modulo square-free odd integers. Inf. Process. Lett. 112(22), 872-75 (2012)MathSciNet View Article
  27.Zheng, Q.-X., Qi, W.-F., Tian, T.: On the distinctness of binary sequences derived from primitive sequences modulo square-free odd integers. IEEE Trans. Inf. Theory 59(1), 680-90 (2013)MathSciNet View Article
  28.Zheng, Q.-X., Qi, W.-F.: Further results on the distinctness of binary sequences derived from primitive sequences modulo square-free odd integers. IEEE Trans. Inf. Theory 59(6), 4013-019 (2013)MathSciNet View Ar
• 作者单位：Zhi Hu (1) (2)
  Lin Wang (3)
  
  1. School of Mathematics and Statistics, Central South University, Changsha, 410083, Hunan, People’’s Republic of China
  2. Beijing International Center for Mathematical Research, Peking University, Beijing, 100871, People’s Republic of China
  3. Science and Technology on Communication Security Laboratory, Chengdu, 610041, People’s Republic of China
  
• 刊物类别：Computer Science
• 刊物主题：Coding and Information Theory
  Mathematics of Computing
  
• 出版者：Springer New York
• ISSN：1936-2455

文摘

Let p 1, p 2,-p r be distinct odd primes and m = p 1 p 2?em class="EmphasisTypeItalic">p r . Let f(x) be a primitive polynomial of degree n over \(\mathbb {Z}/m\mathbb {Z}\). Denote by L(f) the set of primitive linear recurring sequences generated by f(x). A map ψ on \(\mathbb {Z}/m\mathbb {Z}\) naturally induces a map \(\widehat {\psi }\) on L(f), mapping a sequence \((\dots ,\underline {s}({i-1}),\underline {s}(i),\underline {s}({i+1}),\dots )\) to \((\dots ,\psi (\underline {s}({i-1})),\psi (\underline {s}(i)),\psi (\underline {s}({i+1})),\dots )\). Previous results gave sufficient conditions under which modular functions induce injective maps on L(f). In this article we give an inequality which holds for large enough n. If this inequality holds, then the injectivity of \(\hat {\psi }\) is clearly determined for any map ψ on \(\mathbb {Z}/m\mathbb {Z}\). Particularly, the modular function ψ(a)=a mod M induces an injective map on L(f) for any \(M\in \left \{{2\leq i\in \mathbb {Z}:i \nmid m}\right \}\).