›› 2011, Vol. 26 ›› Issue (2): 276-282.doi: 10.1007/s11390-011-1130-y

• Computer Network and Information Security • Previous Articles     Next Articles

Pseudo-Randomness of Certain Sequences of k Symbols with Length pq

Zhi-Xiong Chen1,2 (陈智雄), Member, CCF, Xiao-Ni Du2,3 (杜小妮), and Chen-Huang Wu1 (吴晨煌), Member, CCF   

  1. 1. Department of Mathematics, Putian University, Putian 351100, China;
    2. State Key Lab. of ISN, Xidian University, Xi'an 710071, China;
    3. College of Mathematics and Information Science, Northwest Normal University, Lanzhou 30070, China
  • Received:2010-03-24 Revised:2010-11-25 Online:2011-03-05 Published:2011-03-05
  • About author:Zhi-Xiong Chen was born in 1972 in Fujian province of China. He received the M.S. degree in mathematics from Fujian Normal University in 1999 and Ph.D. degree in cryptography from Xidian University, China, in 2006, respectively. Now he is an associate professor of Putian University. He is a member of CCF and CACR. His research interests include stream ciphers and elliptic curve cryptography.
    Xiao-Ni Du was born in 1972 in Gansu province of China. She received the M.S. degree in computer science from Lanzhou University in 2000 and Ph.D. degree in cryptography from Xidian University, China, in 2008, respectively. Now she is an associate professor of Northwest Normal University. Her research interests include cryptology and information security.
    Chen-Huang Wu was born in 1981 in Fujian province of China. He received the M.S. degree in mathematics from Zhangzhou Normal University in 2007. Now he is a lecturer of Putian University. He is a member of CCF and CACR. His research interests include digital signatures and elliptic curve cryptography.
  • Supported by:

    The work was partially supported by the National Natural Science Foundation of China under Grant No. 61063041, the Program for New Century Excellent Talents of Universities in Fujian Province under Grant No. JK2010047 and the Funds of the Education Department of Gansu Province under Grant No. 1001-09.

The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sárközy and later extended to sequences of k symbols (or k-ary sequences). Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.

[1] Mauduit C, Sárközy A. On finite pseudo-random binary sequences I: Measures of pseudo-randomness, the Legendre symbol. Acta Arithmetica, 1997, 82: 365-377.

[2] Cassaigne J, Mauduit C, Sárközy A. On finite pseudo-random binary sequences, VII: The measures of pseudo-randomness. Acta Arithmetica, 2002, 103(2): 97-118.

[3] Mauduit C, Sarközy A. On finite pseudo-random sequences of k symbols. Indagationes Mathematicae-New Series, 2002, 13(1): 89-101.

[4] Ahlswede R, Mauduit C, Sárközy A. Large Families of Pseudorandom Sequences of k Symbols and Their Complexity, Part I. General Theory of Information Transfer and Combinatorics, LNCS 4123, Springer-Verlag, 2006, pp.293-307.

[5] Ahlswede R, Mauduit C, Sárközy A. Large Families of Pseudorandom Sequences of k Symbols and Their Complexity, Part II. General Theory of Information Transfer and Combinatorics, LNCS 4123, Springer-Verlag, 2006, pp.308-325.

[6] Bérczi G. On finite pseudo-random sequences of k symbols. Periodica Mathematica Hungarica, 2003, 47(1/2): 29-44.

[7] Mérai L. On finite pseudo-random lattices of k symbols. Monatshefte für Mathematik, 2010, 161(2): 173-191.

[8] Rivat J, Sárközy A. Modular constructions of pseudo-random binary sequences with composite moduli. Periodica Mathematica Hungarica, 2005, 51(2): 75-107.

[9] Brandstätter N, Winterhof A. Some notes on the two-prime generator of order 2. IEEE Transactions on Information Theory, 2005, 51(10): 3654-3657.

[10] Chen Z, Du X, Xiao G. Sequences related to Legendre/Jacobi sequences. Information Sciences, 2007, 177(21): 4820-4831.

[11] Chen Z, Li S. Some notes on generalized cyclotomic sequences of length pq. Journal of Computer Science and Technology, 2008, 23(5): 843-850.

[12] Ding C. Linear complexity of generalized cyclotomic binary sequences of order 2. Finite Fields and Their Applications, 1997, 3(2): 159-174.

[13] Ding C. Autocorrelation values of generalized cyclotomic sequences of order two. IEEE Transactions on Information Theory, 1998, 44(4): 1699-1702.

[14] Du X, Chen Z. Trace representations of generalized cyclotomic sequences of length pq with arbitrary order. Chinese Journal of Electronics, 2009, 18(3): 460-464. (In Chinese)

[15] Yan T, Du X, Xiao G, Huang X. Linear complexity of binary Whiteman generalized cyclotomic sequences of order 2k. Information Sciences, 2009, 179(7): 1019-1023.

[16] Green D H, Green P R. Polyphase related-prime sequences. IEE Proceedings: Computers and Digital Techniques, 2001, 148(2): 53-62.

[17] Hu Y, Wei S, Xiao G. On the linear complexity of generalised Legendre/Jacobi sequences. Acta Electronica Sinica, 2002, 8(2): 113-117. (In Chinese)

[18] Winterhof A. Linear Complexity and Related Complexity Measures. Selected Topics in Information and Coding Theory, Singapore: World Scientific, 2010, pp.3-40.

[19] Lidl R, Niederreiter H. Finite Fields. Cambridge: Cambridge Univ. Press, 1997.

[20] Niederreiter H. Linear complexity and related complexity measures for sequences. In Proc. INDOCRYPT 2003, New Delhi, India, Dec. 8-10, 2003, pp.1-17.

[21] Chen Z, Winterhof A. Linear complexity profile of m-ary pseudo-random sequences with small correlation measure. Indagationes Mathematicae-New Series, 2010. (To appear)

[22] Chen Z, Du X. Linear complexity and autocorrelation values of a polyphase generalized cyclotomic sequence of length pq. Frontiers of Computer Science in China, 2010, 4(4): 529-535.

[23] Ding C. New generalized cyclotomy and its applications. Finite Fields and Their Applications, 1998, 4(2): 140-166.

[24] Meidl W. Remarks on a cyclotomic sequence. Design Codes and Cryptography, 2009, 51(1): 33-43.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved