We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Zhi-Xiong Chen, Xiao-Ni Du, Chen-Huang Wu. Pseudo-Randomness of Certain Sequences of k Symbols with Length pq[J]. Journal of Computer Science and Technology, 2011, 26(2): 276-282. DOI: 10.1007/s11390-011-1130-y
Citation: Zhi-Xiong Chen, Xiao-Ni Du, Chen-Huang Wu. Pseudo-Randomness of Certain Sequences of k Symbols with Length pq[J]. Journal of Computer Science and Technology, 2011, 26(2): 276-282. DOI: 10.1007/s11390-011-1130-y

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

Funds: 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.
More Information
  • Author Bio:

    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.

  • Received Date: March 23, 2010
  • Revised Date: November 24, 2010
  • Published Date: March 04, 2011
  • 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.
  • Related Articles

    [1]Jian-Hua Gao. Clausal Presentation of Theories in Deduction Modulo[J]. Journal of Computer Science and Technology, 2013, 28(6): 1085-1096. DOI: 10.1007/s11390-013-1399-0
    [2]Zhi-Xiong Chen, Sheng-Qiang Li. Some Notes on Generalized Cyclotomic Sequences of Length pq[J]. Journal of Computer Science and Technology, 2008, 23(5): 843-850.
    [3]Xia-Fen Zhang, Yue-Ting Zhuang, Jiang-Qin Wu, Fei Wu. Hierarchical Approximate Matching for Retrieval of Chinese Historical Calligraphy Character[J]. Journal of Computer Science and Technology, 2007, 22(4): 633-640.
    [4]Abbas H. Hassin, Xiang-Long Tang, Jia-Feng Liu, Wei Zhao. Printed Arabic Character Recognition Using HMM[J]. Journal of Computer Science and Technology, 2004, 19(4).
    [5]XU Zhiming, WANG Xiaolong. A New Linguistic Decoding Method for Online Handwritten Chinese Character Recognition[J]. Journal of Computer Science and Technology, 2000, 15(6): 597-604.
    [6]XU Zhiming, WANG Xiaolong. A New Linguistic Decoding Method for Online Handwritten Chinese Character Recognition[J]. Journal of Computer Science and Technology, 2000, 15(6).
    [7]Zheng Fang, Wu Wenhu, Fang Ditang. A Log-Index Weighted Cepstral Distance Measure for Speech Recognition[J]. Journal of Computer Science and Technology, 1997, 12(2): 177-184.
    [8]Zeng Jianchao, Hidehilio Sanada, Yoshikazu Tezuka. A Form Evaluation System and Its Data Structure for Brush-Written Chinese Characters[J]. Journal of Computer Science and Technology, 1995, 10(1): 35-41.
    [9]Huang Xuedong, Cai Lianhong, Fang Ditang, Chi Bianjin, Zhou Li, Jiang Li. A Computer System for Chinese Character Speech Input[J]. Journal of Computer Science and Technology, 1986, 1(4): 75-83.
    [10]Wang Xuan, Lü Zhimin, Tang Yuhai, Xiang Yang. A High Resolution Chinese Character Generator[J]. Journal of Computer Science and Technology, 1986, 1(2): 1-14.

Catalog

    Article views (20) PDF downloads (1914) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return