• Previous Article
    Cryptanalysis of a 2-party key establishment based on a semigroup action problem
  • AMC Home
  • This Issue
  • Next Article
    Infinite families of optimal splitting authentication codes secure against spoofing attacks of higher order
February  2011, 5(1): 69-86. doi: 10.3934/amc.2011.5.69

The enumeration of Costas arrays of order 28 and its consequences

1. 

School of Electrical, Electronic & Mechanical Engineering, University College Dublin, Belfield, Dublin 4

2. 

Autodesk Research, 210 King Street East, Toronto, Ontario M5A 1J7, Canada

Received  July 2010 Published  February 2011

The results of the enumeration of Costas arrays of order 28 are presented: all arrays found are accounted for by the Golomb and Welch construction methods, making 28 the first order (larger than 5) for which no sporadic Costas arrays exist. The enumeration was performed on several computer clusters and required the equivalent of 70 years of single CPU time. Furthermore, a classification of Costas arrays in four classes is proposed, and it is conjectured, based on the results of the enumeration combined with further evidence, that two of them eventually become extinct.
Citation: Konstantinos Drakakis, Francesco Iorio, Scott Rickard. The enumeration of Costas arrays of order 28 and its consequences. Advances in Mathematics of Communications, 2011, 5 (1) : 69-86. doi: 10.3934/amc.2011.5.69
References:
[1]

L. Barker, K. Drakakis and S. Rickard, On the complexity of the verification of the Costas property,, Proc. IEEE, 97 (2009), 586.  doi: 10.1109/JPROC.2008.2011947.  Google Scholar

[2]

J. K. Beard, Private communication,, May 2008., (2008).   Google Scholar

[3]

J. K. Beard, J. C. Russo, K. G. Erickson, M. C. Monteleone and M. T. Wright, Costas arrays generation and search methodology,, IEEE Trans. Aerospace Electr. Systems, 43 (2007), 522.  doi: 10.1109/TAES.2007.4285351.  Google Scholar

[4]

C. Brown, M. Cenki, R. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays,, in, (1993).  doi: 10.1109/ISIT.1993.748721.  Google Scholar

[5]

S. Cohen and G. Mullen, Primitive elements in finite fields and Costas arrays,, Appl. Algebra Engin. Commun. Comput., 2 (1991), 45.  doi: 10.1007/BF01810854.  Google Scholar

[6]

J. P. Costas, Medium constraints on SONAR design and performance,, in, (1975).   Google Scholar

[7]

J. P. Costas, A study of detection waveforms having nearly ideal range-doppler ambiguity properties,, Proc. IEEE, 72 (1984), 996.  doi: 10.1109/PROC.1984.12967.  Google Scholar

[8]

K. Drakakis, A review of Costas arrays,, J. Appl. Math., 2006 ().   Google Scholar

[9]

K. Drakakis, R. Gow and L. O'Carroll, On the symmetry of Welch- and Golomb-constructed Costas arrays,, Discrete Math., 309 (2009), 2559.  doi: 10.1016/j.disc.2008.04.058.  Google Scholar

[10]

K. Drakakis, S. Rickard, J. Beard, R. Caballero, F. Iorio, G. O'Brien and J. Walsh, Results of the enumeration of Costas arrays of order 27,, IEEE Trans. Inform. Theory, 54 (2008), 4684.  doi: 10.1109/TIT.2008.928979.  Google Scholar

[11]

S. W. Golomb, Algebraic constructions for Costas arrays,, J. Combin. Theory Ser. A, 37 (1984), 13.  doi: 10.1016/0097-3165(84)90015-3.  Google Scholar

[12]

S. W. Golomb, The $T_4$ and $G_4$ constructions for Costas arrays,, IEEE Trans. Inform. Theory, 38 (1992), 1404.  doi: 10.1109/18.144726.  Google Scholar

[13]

S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays,, Proc. IEEE, 72 (1984), 1143.  doi: 10.1109/PROC.1984.12994.  Google Scholar

[14]

K. Ireland and M. Rosen, "A Classical Introduction to Modern Number Theory,'' $2^{nd}$ edition,, Springer, (1990).   Google Scholar

[15]

S. Rickard, Searching for Costas arrays using periodicity properties,, in, (2004).   Google Scholar

[16]

S. Rickard, Open problems in Costas arrays,, in, (2006).   Google Scholar

[17]

S. Rickard, E. Connell, F. Duignan, B. Ladendorf and A. Wade, The enumeration of Costas arrays of size 26,, in, (2006).  doi: 10.1109/CISS.2006.286579.  Google Scholar

[18]

J. Silverman, V. Vickers and J. Mooney, On the number of Costas arrays as a function of array size,, Proc. IEEE, 76 (1988), 851.  doi: 10.1109/5.7156.  Google Scholar

[19]

K. Taylor, K. Drakakis and S. Rickard, Generated, emergent, and sporadic Costas arrays,, in, (2008).   Google Scholar

show all references

References:
[1]

L. Barker, K. Drakakis and S. Rickard, On the complexity of the verification of the Costas property,, Proc. IEEE, 97 (2009), 586.  doi: 10.1109/JPROC.2008.2011947.  Google Scholar

[2]

J. K. Beard, Private communication,, May 2008., (2008).   Google Scholar

[3]

J. K. Beard, J. C. Russo, K. G. Erickson, M. C. Monteleone and M. T. Wright, Costas arrays generation and search methodology,, IEEE Trans. Aerospace Electr. Systems, 43 (2007), 522.  doi: 10.1109/TAES.2007.4285351.  Google Scholar

[4]

C. Brown, M. Cenki, R. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays,, in, (1993).  doi: 10.1109/ISIT.1993.748721.  Google Scholar

[5]

S. Cohen and G. Mullen, Primitive elements in finite fields and Costas arrays,, Appl. Algebra Engin. Commun. Comput., 2 (1991), 45.  doi: 10.1007/BF01810854.  Google Scholar

[6]

J. P. Costas, Medium constraints on SONAR design and performance,, in, (1975).   Google Scholar

[7]

J. P. Costas, A study of detection waveforms having nearly ideal range-doppler ambiguity properties,, Proc. IEEE, 72 (1984), 996.  doi: 10.1109/PROC.1984.12967.  Google Scholar

[8]

K. Drakakis, A review of Costas arrays,, J. Appl. Math., 2006 ().   Google Scholar

[9]

K. Drakakis, R. Gow and L. O'Carroll, On the symmetry of Welch- and Golomb-constructed Costas arrays,, Discrete Math., 309 (2009), 2559.  doi: 10.1016/j.disc.2008.04.058.  Google Scholar

[10]

K. Drakakis, S. Rickard, J. Beard, R. Caballero, F. Iorio, G. O'Brien and J. Walsh, Results of the enumeration of Costas arrays of order 27,, IEEE Trans. Inform. Theory, 54 (2008), 4684.  doi: 10.1109/TIT.2008.928979.  Google Scholar

[11]

S. W. Golomb, Algebraic constructions for Costas arrays,, J. Combin. Theory Ser. A, 37 (1984), 13.  doi: 10.1016/0097-3165(84)90015-3.  Google Scholar

[12]

S. W. Golomb, The $T_4$ and $G_4$ constructions for Costas arrays,, IEEE Trans. Inform. Theory, 38 (1992), 1404.  doi: 10.1109/18.144726.  Google Scholar

[13]

S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays,, Proc. IEEE, 72 (1984), 1143.  doi: 10.1109/PROC.1984.12994.  Google Scholar

[14]

K. Ireland and M. Rosen, "A Classical Introduction to Modern Number Theory,'' $2^{nd}$ edition,, Springer, (1990).   Google Scholar

[15]

S. Rickard, Searching for Costas arrays using periodicity properties,, in, (2004).   Google Scholar

[16]

S. Rickard, Open problems in Costas arrays,, in, (2006).   Google Scholar

[17]

S. Rickard, E. Connell, F. Duignan, B. Ladendorf and A. Wade, The enumeration of Costas arrays of size 26,, in, (2006).  doi: 10.1109/CISS.2006.286579.  Google Scholar

[18]

J. Silverman, V. Vickers and J. Mooney, On the number of Costas arrays as a function of array size,, Proc. IEEE, 76 (1988), 851.  doi: 10.1109/5.7156.  Google Scholar

[19]

K. Taylor, K. Drakakis and S. Rickard, Generated, emergent, and sporadic Costas arrays,, in, (2008).   Google Scholar

[1]

Konstantinos Drakakis, Francesco Iorio, Scott Rickard, John Walsh. Results of the enumeration of Costas arrays of order 29. Advances in Mathematics of Communications, 2011, 5 (3) : 547-553. doi: 10.3934/amc.2011.5.547

[2]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020184

[3]

Jonathan Jedwab, Jane Wodlinger. Structural properties of Costas arrays. Advances in Mathematics of Communications, 2014, 8 (3) : 241-256. doi: 10.3934/amc.2014.8.241

[4]

Konstantinos Drakakis, Roderick Gow, Scott Rickard. Common distance vectors between Costas arrays. Advances in Mathematics of Communications, 2009, 3 (1) : 35-52. doi: 10.3934/amc.2009.3.35

[5]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020196

[6]

Konstantinos Drakakis, Rod Gow, Scott Rickard. Parity properties of Costas arrays defined via finite fields. Advances in Mathematics of Communications, 2007, 1 (3) : 321-330. doi: 10.3934/amc.2007.1.321

[7]

Henning Struchtrup. Unique moment set from the order of magnitude method. Kinetic & Related Models, 2012, 5 (2) : 417-440. doi: 10.3934/krm.2012.5.417

[8]

Min Tang. Second order all speed method for the isentropic Euler equations. Kinetic & Related Models, 2012, 5 (1) : 155-184. doi: 10.3934/krm.2012.5.155

[9]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2019  doi: 10.3934/jimo.2019115

[10]

Yong Li, Catalin Trenchea. Partitioned second order method for magnetohydrodynamics in Elsässer variables. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2803-2823. doi: 10.3934/dcdsb.2018106

[11]

Guoshan Zhang, Peizhao Yu. Lyapunov method for stability of descriptor second-order and high-order systems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 673-686. doi: 10.3934/jimo.2017068

[12]

Lijun Yi, Zhongqing Wang. Legendre spectral collocation method for second-order nonlinear ordinary/partial differential equations. Discrete & Continuous Dynamical Systems - B, 2014, 19 (1) : 299-322. doi: 10.3934/dcdsb.2014.19.299

[13]

Ugur G. Abdulla. On the optimal control of the free boundary problems for the second order parabolic equations. II. Convergence of the method of finite differences. Inverse Problems & Imaging, 2016, 10 (4) : 869-898. doi: 10.3934/ipi.2016025

[14]

Kazuyuki Yagasaki. Higher-order Melnikov method and chaos for two-degree-of-freedom Hamiltonian systems with saddle-centers. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 387-402. doi: 10.3934/dcds.2011.29.387

[15]

Anis Theljani, Ke Chen. An augmented lagrangian method for solving a new variational model based on gradients similarity measures and high order regulariation for multimodality registration. Inverse Problems & Imaging, 2019, 13 (2) : 309-335. doi: 10.3934/ipi.2019016

[16]

Xiao-Yu Zhang, Qing Fang. A sixth order numerical method for a class of nonlinear two-point boundary value problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 31-43. doi: 10.3934/naco.2012.2.31

[17]

Klemens Fellner, Wolfang Prager, Bao Q. Tang. The entropy method for reaction-diffusion systems without detailed balance: First order chemical reaction networks. Kinetic & Related Models, 2017, 10 (4) : 1055-1087. doi: 10.3934/krm.2017042

[18]

Ben-Yu Guo, Zhong-Qing Wang. A spectral collocation method for solving initial value problems of first order ordinary differential equations. Discrete & Continuous Dynamical Systems - B, 2010, 14 (3) : 1029-1054. doi: 10.3934/dcdsb.2010.14.1029

[19]

Netra Khanal, Ramjee Sharma, Jiahong Wu, Juan-Ming Yuan. A dual-Petrov-Galerkin method for extended fifth-order Korteweg-de Vries type equations. Conference Publications, 2009, 2009 (Special) : 442-450. doi: 10.3934/proc.2009.2009.442

[20]

Juan-Ming Yuan, Jiahong Wu. A dual-Petrov-Galerkin method for two integrable fifth-order KdV type equations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (4) : 1525-1536. doi: 10.3934/dcds.2010.26.1525

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (65)
  • HTML views (0)
  • Cited by (11)

[Back to Top]