August  2014, 8(3): 297-312. doi: 10.3934/amc.2014.8.297

Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3)

1. 

Department of Mathematics, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China, China

2. 

Science and Technology on Information Assurance Laboratory, Beijing, 100072, China

Received  April 2013 Revised  December 2013 Published  August 2014

In this paper, we always assume that $p=6f+1$ is a prime. First, we calculate the values of exponential sums of cyclotomic classes of orders 3 and 6 over an extension field of GF(3). Then, we give a formula to compute the linear complexity of all $p^{n+1}$-periodic generalized cyclotomic sequences of order 6 over GF(3). After that, we compute the linear complexity and the minimal polynomial of a $p^{n+1}$-periodic, balanced and generalized cyclotomic sequence of order 6 over GF(3), which is analogous to a generalized Sidelnikov's sequence. At last, we give some BCH codes with prime length $p$ from cyclotomic sequences of orders three and six.
Citation: Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297
References:
[1]

E. Bai, X. Liu and G. Xiao, Linear complexity of new generalized cyclotomic sequences of order two of length pq,, IEEE Trans. Inform. Theory, 51 (2005), 1849.  doi: 10.1109/TIT.2005.846450.  Google Scholar

[2]

B. C. Berndt, R. J. Evans and K. S. Williams, Gauss and Jacobi Sums,, J. Wiley and Sons Company, (1997).   Google Scholar

[3]

C. Ding, Linear complexity of generalized cyclotomic binary sequences of order $2$,, Finite Fields Appl., 3 (1997), 159.  doi: 10.1006/ffta.1997.0181.  Google Scholar

[4]

C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two,, IEEE Trans. Inform. Theory, 44 (1998), 1698.  doi: 10.1109/18.681354.  Google Scholar

[5]

C. Ding, Pattern distribution of Legendre sequences,, IEEE Trans. Inform. Theory, 44 (1998), 1693.  doi: 10.1109/18.681353.  Google Scholar

[6]

C. Ding, The weight distribution of some irreducible cyclic codes,, IEEE Trans. Inform. Theory, 55 (2009), 955.  doi: 10.1109/TIT.2008.2011511.  Google Scholar

[7]

C. Ding, Cyclic codes from cyclotomic sequences of order four,, Finite Fields Appl., 23 (2013), 8.  doi: 10.1016/j.ffa.2013.03.006.  Google Scholar

[8]

C. Ding and T. Helleseth, New generalized cyclotomy and its applications,, Finite Fields Appl., 4 (1998), 140.  doi: 10.1006/ffta.1998.0207.  Google Scholar

[9]

C. Ding, T. Helleseth and K. Y. Lam, Several classes of sequences with three-level autocorrelation,, IEEE Trans. Inform. Theory, 45 (1999), 2606.  doi: 10.1109/18.796414.  Google Scholar

[10]

C. Ding, T. Helleseth and H. M. Martinsen, New families of binary sequences with optimal three-level autocorrelation,, IEEE Trans. Inform. Theory, 47 (2001), 428.  doi: 10.1109/18.904555.  Google Scholar

[11]

L. E. Dickson, Cyclotomy, higher congruences and Waring's problem,, Amer. J. math., 57 (1935), 391.  doi: 10.2307/2371217.  Google Scholar

[12]

V. A. Edemskii, On the linear complexity of binary sequences on the basis of biquadratic and sextic residue classes,, Discrete Math. Appl., 20 (2010), 75.  doi: 10.1515/DMA.2010.004.  Google Scholar

[13]

V. A. Edemskii, About computation of the linear complexity of generalized cyclotomic sequences with period $p^{n+1}$,, Des. Codes Cryptogr., 61 (2011), 251.  doi: 10.1007/s10623-010-9474-9.  Google Scholar

[14]

K. Feng and F. Liu, Algebra and Communication,, Higher education press, (2005).   Google Scholar

[15]

M. Hall, Combinatorial Theory,, Blaisdell Company, (1967).   Google Scholar

[16]

K. Ireland and M. Rosen, A classical introduction to modern number theory, Second edition,, Springer-Verlag, (2003).  doi: 10.1007/978-1-4757-2103-4.  Google Scholar

[17]

J. H. Kim and H. Y. Song, On the linear complexity of Hall's sextic residue sequences,, IEEE Trans. Inform. Theory, 47 (2001), 2094.  doi: 10.1109/18.930950.  Google Scholar

[18]

A. Lempel, M. Cohn and W. L. Estman, A class of binary sequences with optimal autocorrelation properties,, IEEE Trans. Inform. Theory, 23 (1997), 38.  doi: 10.1109/TIT.1977.1055672.  Google Scholar

[19]

R. Lidl and H. Niederreiter, Finite Fields,, Addison-Wesley Publishing Company, (1983).   Google Scholar

[20]

F. Liu, D. Y. Peng, X. H. Tang and X. H. Niu, On the autocorrelation and the linear complexity of $q$-ary prime $n$-square sequences,, in Sequences and their Applications- SETA 2010, (2010), 139.  doi: 10.1007/978-3-642-15874-2_11.  Google Scholar

[21]

V. M. Sidelnikov, Some k-valued pseudo-random sequences and nearly equidistance codes,, Probl. Inform. Transm., 5 (1969), 12.   Google Scholar

[22]

A. L. Whiteman, The cyclotomic numbers of order twelve,, Acta Arith., 6 (1960), 53.   Google Scholar

show all references

References:
[1]

E. Bai, X. Liu and G. Xiao, Linear complexity of new generalized cyclotomic sequences of order two of length pq,, IEEE Trans. Inform. Theory, 51 (2005), 1849.  doi: 10.1109/TIT.2005.846450.  Google Scholar

[2]

B. C. Berndt, R. J. Evans and K. S. Williams, Gauss and Jacobi Sums,, J. Wiley and Sons Company, (1997).   Google Scholar

[3]

C. Ding, Linear complexity of generalized cyclotomic binary sequences of order $2$,, Finite Fields Appl., 3 (1997), 159.  doi: 10.1006/ffta.1997.0181.  Google Scholar

[4]

C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two,, IEEE Trans. Inform. Theory, 44 (1998), 1698.  doi: 10.1109/18.681354.  Google Scholar

[5]

C. Ding, Pattern distribution of Legendre sequences,, IEEE Trans. Inform. Theory, 44 (1998), 1693.  doi: 10.1109/18.681353.  Google Scholar

[6]

C. Ding, The weight distribution of some irreducible cyclic codes,, IEEE Trans. Inform. Theory, 55 (2009), 955.  doi: 10.1109/TIT.2008.2011511.  Google Scholar

[7]

C. Ding, Cyclic codes from cyclotomic sequences of order four,, Finite Fields Appl., 23 (2013), 8.  doi: 10.1016/j.ffa.2013.03.006.  Google Scholar

[8]

C. Ding and T. Helleseth, New generalized cyclotomy and its applications,, Finite Fields Appl., 4 (1998), 140.  doi: 10.1006/ffta.1998.0207.  Google Scholar

[9]

C. Ding, T. Helleseth and K. Y. Lam, Several classes of sequences with three-level autocorrelation,, IEEE Trans. Inform. Theory, 45 (1999), 2606.  doi: 10.1109/18.796414.  Google Scholar

[10]

C. Ding, T. Helleseth and H. M. Martinsen, New families of binary sequences with optimal three-level autocorrelation,, IEEE Trans. Inform. Theory, 47 (2001), 428.  doi: 10.1109/18.904555.  Google Scholar

[11]

L. E. Dickson, Cyclotomy, higher congruences and Waring's problem,, Amer. J. math., 57 (1935), 391.  doi: 10.2307/2371217.  Google Scholar

[12]

V. A. Edemskii, On the linear complexity of binary sequences on the basis of biquadratic and sextic residue classes,, Discrete Math. Appl., 20 (2010), 75.  doi: 10.1515/DMA.2010.004.  Google Scholar

[13]

V. A. Edemskii, About computation of the linear complexity of generalized cyclotomic sequences with period $p^{n+1}$,, Des. Codes Cryptogr., 61 (2011), 251.  doi: 10.1007/s10623-010-9474-9.  Google Scholar

[14]

K. Feng and F. Liu, Algebra and Communication,, Higher education press, (2005).   Google Scholar

[15]

M. Hall, Combinatorial Theory,, Blaisdell Company, (1967).   Google Scholar

[16]

K. Ireland and M. Rosen, A classical introduction to modern number theory, Second edition,, Springer-Verlag, (2003).  doi: 10.1007/978-1-4757-2103-4.  Google Scholar

[17]

J. H. Kim and H. Y. Song, On the linear complexity of Hall's sextic residue sequences,, IEEE Trans. Inform. Theory, 47 (2001), 2094.  doi: 10.1109/18.930950.  Google Scholar

[18]

A. Lempel, M. Cohn and W. L. Estman, A class of binary sequences with optimal autocorrelation properties,, IEEE Trans. Inform. Theory, 23 (1997), 38.  doi: 10.1109/TIT.1977.1055672.  Google Scholar

[19]

R. Lidl and H. Niederreiter, Finite Fields,, Addison-Wesley Publishing Company, (1983).   Google Scholar

[20]

F. Liu, D. Y. Peng, X. H. Tang and X. H. Niu, On the autocorrelation and the linear complexity of $q$-ary prime $n$-square sequences,, in Sequences and their Applications- SETA 2010, (2010), 139.  doi: 10.1007/978-3-642-15874-2_11.  Google Scholar

[21]

V. M. Sidelnikov, Some k-valued pseudo-random sequences and nearly equidistance codes,, Probl. Inform. Transm., 5 (1969), 12.   Google Scholar

[22]

A. L. Whiteman, The cyclotomic numbers of order twelve,, Acta Arith., 6 (1960), 53.   Google Scholar

[1]

Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667

[2]

Van Cyr, Bryna Kra. The automorphism group of a minimal shift of stretched exponential growth. Journal of Modern Dynamics, 2016, 10: 483-495. doi: 10.3934/jmd.2016.10.483

[3]

Valery Y. Glizer, Oleg Kelis. Singular infinite horizon zero-sum linear-quadratic differential game: Saddle-point equilibrium sequence. Numerical Algebra, Control & Optimization, 2017, 7 (1) : 1-20. doi: 10.3934/naco.2017001

[4]

Yuk L. Yung, Cameron Taketa, Ross Cheung, Run-Lie Shia. Infinite sum of the product of exponential and logarithmic functions, its analytic continuation, and application. Discrete & Continuous Dynamical Systems - B, 2010, 13 (1) : 229-248. doi: 10.3934/dcdsb.2010.13.229

[5]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

[6]

Van Cyr, John Franks, Bryna Kra, Samuel Petite. Distortion and the automorphism group of a shift. Journal of Modern Dynamics, 2018, 13: 147-161. doi: 10.3934/jmd.2018015

[7]

Diego F. Aranha, Ricardo Dahab, Julio López, Leonardo B. Oliveira. Efficient implementation of elliptic curve cryptography in wireless sensors. Advances in Mathematics of Communications, 2010, 4 (2) : 169-187. doi: 10.3934/amc.2010.4.169

[8]

Andreas Klein. How to say yes, no and maybe with visual cryptography. Advances in Mathematics of Communications, 2008, 2 (3) : 249-259. doi: 10.3934/amc.2008.2.249

[9]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281

[10]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489

[11]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012

[12]

Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015

[13]

Daniel Gonçalves, Marcelo Sobottka. Continuous shift commuting maps between ultragraph shift spaces. Discrete & Continuous Dynamical Systems - A, 2019, 39 (2) : 1033-1048. doi: 10.3934/dcds.2019043

[14]

Michael Schraudner. Projectional entropy and the electrical wire shift. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 333-346. doi: 10.3934/dcds.2010.26.333

[15]

Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036

[16]

James Kingsbery, Alex Levin, Anatoly Preygel, Cesar E. Silva. Dynamics of the $p$-adic shift and applications. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 209-218. doi: 10.3934/dcds.2011.30.209

[17]

Christian Wolf. A shift map with a discontinuous entropy function. Discrete & Continuous Dynamical Systems - A, 2020, 40 (1) : 319-329. doi: 10.3934/dcds.2020012

[18]

Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013

[19]

Yixiao Qiao, Xiaoyao Zhou. Zero sequence entropy and entropy dimension. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 435-448. doi: 10.3934/dcds.2017018

[20]

Walter Briec, Bernardin Solonandrasana. Some remarks on a successive projection sequence. Journal of Industrial & Management Optimization, 2006, 2 (4) : 451-466. doi: 10.3934/jimo.2006.2.451

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (10)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]