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-1853. doi: 10.1109/TIT.2005.846450.

[2]

B. C. Berndt, R. J. Evans and K. S. Williams, Gauss and Jacobi Sums, J. Wiley and Sons Company, New York, 1997.

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[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-433. doi: 10.1109/18.904555.

[11]

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

[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-84. doi: 10.1515/DMA.2010.004.

[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-260. doi: 10.1007/s10623-010-9474-9.

[14]

K. Feng and F. Liu, Algebra and Communication, Higher education press, Beijing, 2005.

[15]

M. Hall, Combinatorial Theory, Blaisdell Company, Waltham, 1967.

[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.

[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-2096. doi: 10.1109/18.930950.

[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-42. doi: 10.1109/TIT.1977.1055672.

[19]

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley Publishing Company, 1983.

[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-150, doi: 10.1007/978-3-642-15874-2_11.

[21]

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

[22]

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

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-1853. doi: 10.1109/TIT.2005.846450.

[2]

B. C. Berndt, R. J. Evans and K. S. Williams, Gauss and Jacobi Sums, J. Wiley and Sons Company, New York, 1997.

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[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-433. doi: 10.1109/18.904555.

[11]

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

[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-84. doi: 10.1515/DMA.2010.004.

[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-260. doi: 10.1007/s10623-010-9474-9.

[14]

K. Feng and F. Liu, Algebra and Communication, Higher education press, Beijing, 2005.

[15]

M. Hall, Combinatorial Theory, Blaisdell Company, Waltham, 1967.

[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.

[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-2096. doi: 10.1109/18.930950.

[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-42. doi: 10.1109/TIT.1977.1055672.

[19]

R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley Publishing Company, 1983.

[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-150, doi: 10.1007/978-3-642-15874-2_11.

[21]

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

[22]

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

[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]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044

[3]

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

[4]

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

[5]

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 and Continuous Dynamical Systems - B, 2010, 13 (1) : 229-248. doi: 10.3934/dcdsb.2010.13.229

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[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]

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

[13]

Anna-Lena Horlemann-Trautmann, Violetta Weger. Information set decoding in the Lee metric with applications to cryptography. Advances in Mathematics of Communications, 2021, 15 (4) : 677-699. doi: 10.3934/amc.2020089

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 0.935

Metrics

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

Other articles
by authors

[Back to Top]