Divisibility of polynomials over finite fields and combinatorial applications
Consider a maximum-length shift-register sequence generated by a primitive polynomial f over a finite field. The set of its subintervals is a linear code whose dual code is formed by all polynomials divisible by f . Since theminimum weight of dual codes is directly related to the strength of the corresponding orthogonal arrays, we can produce orthogonal arrays by studying divisibility of polynomials.Munemasa (Finite Fields Appl 4(3):252-260, 1998) uses trinomials over F2 to construct orthogonal arrays of guaranteed strength 2 (and almost strength 3). That result was extended by Dewar et al. (Des Codes Cryptogr 45:1-17, 2007) to construct orthogonal arrays of guaranteed strength 3 by considering divisibility of trinomials by pentanomials over F2. Here we first simplify the requirement in Munemasa's approach that the characteristic polynomial of the sequence must be primitive: we show that the method applies even to the much broader class of polynomials with no repeated roots. Then we give characterizations of divisibility for binomials and trinomials over F 3. Some of our results apply to any finite field Fq with q elements.
|Keywords||Divisibility of polynomials, Orthogonal arrays, Polynomials over finite fields|
|Journal||Designs, Codes and Cryptography|
Panario, D. (Daniel), Sosnovski, O. (Olga), Stevens, B, & Wang, Q. (2012). Divisibility of polynomials over finite fields and combinatorial applications. Designs, Codes and Cryptography, 63(3), 425–445. doi:10.1007/s10623-011-9565-2