The enumeration of Costas arrays of order 28 and its consequences

Konstantinos Drakakis; Francesco Iorio; Scott Rickard

doi:10.3934/amc.2011.5.69

Article Contents

2011, Volume 5, Issue 1: 69-86. Doi: 10.3934/amc.2011.5.69

This issue Previous Article Infinite families of optimal splitting authentication codes secure against spoofing attacks of higher order Next Article Cryptanalysis of a 2-party key establishment based on a semigroup action problem

The enumeration of Costas arrays of order 28 and its consequences

1.
School of Electrical, Electronic & Mechanical Engineering, University College Dublin, Belﬁeld, Dublin 4
2.
Autodesk Research, 210 King Street East, Toronto, Ontario M5A 1J7

Received: June 30, 2010

Published: January 2011

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 05A15, 05B10; Secondary: 05A05, 11B50.

Citation:

Related Papers

Cited by

References

[1]	L. Barker, K. Drakakis and S. Rickard, On the complexity of the verification of the Costas property, Proc. IEEE, 97 (2009), 586-593.doi: 10.1109/JPROC.2008.2011947.
[2]	J. K. Beard, Private communication, May 2008.
[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-538.doi: 10.1109/TAES.2007.4285351.
[4]	C. Brown, M. Cenki, R. Games, J. Rushanan, O. Moreno and P. Pei, New enumeration results for Costas arrays, in "IEEE International Symposium on Information Theory,'' (1993), 405.doi: 10.1109/ISIT.1993.748721.
[5]	S. Cohen and G. Mullen, Primitive elements in finite fields and Costas arrays, Appl. Algebra Engin. Commun. Comput., 2 (1991), 45-53.doi: 10.1007/BF01810854.
[6]	J. P. Costas, Medium constraints on SONAR design and performance, in "Technical Report Class 1 Rep. R65EMH33,'' GE Co., 1965; A synopsis of this report appeared in the EASCON Convention Record, (1975), 68A-68L.
[7]	J. P. Costas, A study of detection waveforms having nearly ideal range-doppler ambiguity properties, Proc. IEEE, 72 (1984), 996-1009.doi: 10.1109/PROC.1984.12967.
[8]	K. Drakakis, A review of Costas arrays, J. Appl. Math., 2006, 32.
[9]	K. Drakakis, R. Gow and L. O'Carroll, On the symmetry of Welch- and Golomb-constructed Costas arrays, Discrete Math., 309 (2009), 2559-2563.doi: 10.1016/j.disc.2008.04.058.
[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-4687.doi: 10.1109/TIT.2008.928979.
[11]	S. W. Golomb, Algebraic constructions for Costas arrays, J. Combin. Theory Ser. A, 37 (1984), 13-21.doi: 10.1016/0097-3165(84)90015-3.
[12]	S. W. Golomb, The $T_4$ and $G_4$ constructions for Costas arrays, IEEE Trans. Inform. Theory, 38 (1992), 1404-1406.doi: 10.1109/18.144726.
[13]	S. W. Golomb and H. Taylor, Constructions and properties of Costas arrays, Proc. IEEE, 72 (1984), 1143-1163.doi: 10.1109/PROC.1984.12994.
[14]	K. Ireland and M. Rosen, "A Classical Introduction to Modern Number Theory,'' $2^{nd}$ edition, Springer, 1990.
[15]	S. Rickard, Searching for Costas arrays using periodicity properties, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2004.
[16]	S. Rickard, Open problems in Costas arrays, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2006.
[17]	S. Rickard, E. Connell, F. Duignan, B. Ladendorf and A. Wade, The enumeration of Costas arrays of size 26, in "Conference on Information Signals and Systems,'' Princeton University, USA, 2006.doi: 10.1109/CISS.2006.286579.
[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-853.doi: 10.1109/5.7156.
[19]	K. Taylor, K. Drakakis and S. Rickard, Generated, emergent, and sporadic Costas arrays, in "IMA International Conference on Mathematics in Signal Processing at The Royal Agricultural College,'' Cirencester, UK, 2008.