Covering arrays from m-sequences and character sums
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.
|Keywords||Character sums, Characters over finite fields, Covering arrays, Linear feedback shift register sequences, Primitive polynomials over finite fields|
|Journal||Designs, Codes and Cryptography|
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