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 (Formula presented.) 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.

Additional Metadata
Keywords Character sums, Characters over finite fields, Covering arrays, Linear feedback shift register sequences, Primitive polynomials over finite fields
Persistent URL dx.doi.org/10.1007/s10623-016-0316-2
Journal Designs, Codes and Cryptography
Citation
Tzanakis, G. (Georgios), Moura, L. (Lucia), Panario, D, & Stevens, B. (2016). Covering arrays from m-sequences and character sums. Designs, Codes and Cryptography, 1–20. doi:10.1007/s10623-016-0316-2