Abstract
A covering array of strength t on v symbols is an array with the property that, for every t-set of column vectors, every one of the \(v^t\) possible t-tuples of symbols appears as a row at least once in the sub-array defined by these column vectors. Arrays constructed using m-sequences over a finite field possess many combinatorial properties and have been used to construct various combinatorial objects; see the recent survey Moura et al. (Des Codes Cryptogr 78(1):197–219, 2016). In this paper we construct covering arrays whose elements are the remainder of the division by some integer of the discrete logarithm applied to selected m-sequence elements. Inspired by the work of Colbourn (Des Codes Cryptogr 55(2–3):201–219, 2010), we prove our results by connecting the covering array property to a character sum, and we evaluate this sum by taking advantage of the balanced way in which the m-sequence elements are distributed. Our results include new infinite families of covering arrays of arbitrary strength.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alderson T.L., Bruen A.: Maximal AMDS codes. Appl. Algebra Eng. Commun. Comput. 19(2), 87–98 (2008).
Berndt B.C., Evans R.J., Williams K.S.: Gauss and Jacobi Sums. Wiley, New York (2016).
Bose R.C.: Mathematical theory of the symmetrical factorial design. Sankhya 8, 107–166 (1947).
Bryce R.C., Colbourn C.J.: A density-based greedy algorithm for higher strength covering arrays. Softw. Test. Verif. Reliab. 19(1), 37–53 (2009).
Cohen D.M., Siddhartha R.D., Parelius J., Patton G.C.: The combinatorial design approach to automatic test generation. IEEE Softw. 13(5), 83 (1996).
Colbourn C.J.: Combinatorial aspects of covering arrays. Le Matematiche (Catania) 58, 121–167 (2004).
Colbourn C.J.: Covering arrays from cyclotomy. Des. Codes Cryptogr. 55(2–3), 201–219 (2010).
Colbourn C.J., Dinitz J.H.: CRC Handbook of Combinatorial Designs. CRC Press, Boca Raton (2010).
Colbourn C.J.: Covering array tables. www.public.asu.edu/ccolbou/src/tabby/catable.html.
De Boer M.A.: Almost MDS codes. Des. Codes Cryptogr. 9(2), 143–155 (1996).
Dewar M., Moura L., Panario D., Stevens B., Wang Q.: Division of trinomials by pentanomials and orthogonal arrays. Des. Codes Cryptogr. 45(1), 1–17 (2007).
Ebert G.L.: Partitioning projective geometries into caps. Can. J. Math. 37(6), 1163–1175 (1985).
Giulietti, M.: On near-MDS elliptic codes. arXiv:math/0211107 (2002)
Golomb S.W., Gong G.: Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar. Cambridge University Press, Cambridge (2005).
Hedayat A.S., Sloane N.J.A., Stufken J.: Orthogonal Arrays: Theory and Applications. Springer, New York (2012).
Hirschfeld J.W.P., Storme L.: The packing problem in statistics, coding theory and finite projective spaces: update 2001. In: Finite Geometries, pp. 201–246. Springer, New York (2001).
Katona G.O.H.: Two applications (for search theory and truth functions) of Sperner type theorems. Period. Math. Hung. 3(1–2), 19–26 (1973).
Kim R., Song O.H., Ri M.H.: Division of tetranomials by type II pentanomials and orthogonal arrays. Vietnam J. Math. (2016). doi:10.1007/s10013-015-0182-7.
Kleitman D.J., Spencer J.: Families of \(k\)-independent sets. Discret. Math. 6(3), 255–262 (1973).
Kuhn D.R., Wallace D.R., Gallo Jr. A.M.: Software fault interactions and implications for software testing. IEEE Trans. Softw. Eng. 30(6), 418–421 (2004).
Lidl R., Niederreiter H.: Finite Fields, vol. 20. Cambridge University Press, Cambridge (1997).
Moura L., Mullen G.L., Panario D.: Finite field constructions of combinatorial arrays. Des. Codes Cryptogr. 78(1), 197–219 (2016).
Mullen G.L., Panario D.: Handbook of Finite Fields. CRC Press, Boca Raton (2013).
Munemasa A.: Orthogonal arrays, primitive trinomials, and shift-register sequences. Finite Fields Appl. 4(3), 252–260 (1998).
Panario D., Sosnovski O., Stevens B., Wang Q.: Divisibility of polynomials over finite fields and combinatorial applications. Des. Codes Cryptogr. 63(3), 425–445 (2012).
Qvist B.: Some remarks concerning curves of the second degree in a finite plane. Suomalainen Tiedeakatemia 134, 1–27 (1952).
Raaphorst S., Moura L., Stevens B.: A construction for strength-3 covering arrays from linear feedback shift register sequences. Des. Codes Cryptogr. 73(3), 949–968 (2014).
Rényi A.: Foundations of Probability. Wiley, New York (1971).
Stein W.A., Abbott T., Abshoff M.: Sage mathematics software (2011).
Tsfasman M., Vlădut S.G.: Algebraic-Geometric Codes. Kluwer, Dordrecht (1991).
Tzanakis G., Moura L., Panario D., Stevens B.: Constructing new covering arrays from LFSR sequences over finite fields. Discret. Math. 339(3), 1158–1171 (2016).
Acknowledgements
We would like to acknowledge the two anonymous referees whose comments considerably improved the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by C. J. Colbourn.
Rights and permissions
About this article
Cite this article
Tzanakis, G., Moura, L., Panario, D. et al. Covering arrays from m-sequences and character sums. Des. Codes Cryptogr. 85, 437–456 (2017). https://doi.org/10.1007/s10623-016-0316-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-016-0316-2
Keywords
- Covering arrays
- Linear feedback shift register sequences
- Primitive polynomials over finite fields
- Characters over finite fields
- Character sums