Abstract Let F be any field containing the finite field of order q . A q -polynomial L over F is an element of the polynomial ring F [ x ] with the property that all powers of x that appear in L with nonzero coefficient have exponent a power of q . It is well known that given any ordinary polynomial f in F [ x ], there exists a q -polynomial that is divisible by f . We study the smallest degree of such a q -polynomial. This is equivalent to studying the $${{\,\mathrm{\mathbb {F}}\,}}_q$$ F q -span of the roots of f in a splitting field. We relate this quantity to the representation theory of the Galois group of f . As an application we give a simultaneous construction of the binary Golay code of length 24, and the Steiner system on 24 points.

The XL algorithm is an algorithm for solving overdetermined systems of multivariate polynomial equations, which was initially introduced for quadratic equations. However, the algorithm works for polynomials of any degree, and in this paper we will focus on the performance of XL for polynomials of degree ≥3, where the optimal termination value of the parameter D is still unknown. We prove that the XL algorithm terminates at a certain value of D in the case that the number of equations exceeds the number of variables by 1 or 2. We also give strong evidence that this value is best possible, and we show that this value is smaller than the degree of regularity. Part of our analysis requires proving that ordinary multinomials are strongly unimodal, and this result may be of independent interest.

Kloosterman sums are exponential sums on finite fields that have important applications in cryptography and coding theory. We use Stickelberger's theorem and the Gross-Koblitz formula to determine the value of the binary Kloosterman sum at$a$modulo 64, modulo 128, and modulo 256 in terms of coefficients of the characteristic polynomial of$a$.

In this paper we compute the Fourier spectra of some recently discovered binomial almost perfect nonlinear (APN) functions. One consequence of this is the determination of the nonlinearity of the functions, which measures their resistance to linear cryptanalysis. Another consequence is that certain error-correcting codes related to these functions have the same weight distribution as the 2-error-correcting Bose–Chaudury–Hocquenghem (BCH) code. Furthermore, for field extensions of $\mathbb{F}_2$ of odd degree, our results provide an alternative proof of the APN property of the functions.

The authors give a construction of multiblock space-time block codes from cyclic division algebras with a givennth root of unity as the nonnorm element. The construction uses local class field theory. Multiblock codes withMblocks can achieve anM-fold increase in diversity.

A conjecture of Niho states that under certain assumptions the Fourier transform of the function${\rm Tr}(x^{d})$on$\BBF _{2^{n}}$, where$d=(2^{tk}+1)/(2^{k}+1)$, has a spectrum with at most five values. We present a counterexample to this conjecture, and the theory behind finding it. We use the theory of quadratic forms over$\BBF _{2}$.

Certain nonlinear binary codes contain more codewords than any comparable linear code presently known. These include the Kerdock (1972) and Preparata (1968) codes that can be very simply constructed as binary images, under the Gray map, of linear codes over Z/sub 4/ that are defined by means of parity checks involving Galois rings. This paper describes how Fourier transforms on Galois rings and elementary symmetric functions can be used to derive lower bounds on the minimum distance of such codes. These methods and techniques from algebraic geometry are applied to find the exact minimum distance of a family of Z/sub 4/. Linear codes with length 2/sup m/ (m, odd) and size 2(2/sup m+1/-5m-2). The Gray image of the code of length 32 is the best (64, 2/sup 37/) code that is presently known. This paper also determines the exact minimum Lee distance of the linear codes over Z/sub 4/ that are obtained from the extended binary two- and three-error-correcting BCH codes by Hensel lifting. The Gray image of the Hensel lift of the three-error-correcting BCH code of length 32 is the best (64, 2/sup 32/) code that is presently known. This code also determines an extremal 32-dimensional even unimodular lattice.

Binary m-sequences are maximal-length sequences generated by shift registers of length m, that are employed in navigation, radar, and spread-spectrum communication. It is well known that given a pair of distinct m-sequences, the crosscorrelation function must take on at least three values. This correspondence addresses a conjecture made by Helleseth in 1976, that if m is a power of 2, then there are no pairs of binary m-sequences with a 3-valued crosscorrelation function. This conjecture is proved under the assumption that the three correlation values are symmetric about -1.

Binary m-sequences are maximal length sequences generated by shift registers of length m, that are employed in navigation, radar, and spread-spectrum communications systems, because of their crosscorrelation properties. It is well known that given a pair of distinct m-sequences, the crosscorrelation function must take on at least three values. The article considers crosscorrelation functions that take on exactly three values, and where these values are preferred in that they are small. The main result is a proof of a conjecture made by Sarwate and Pursley in 1980, that if m/spl equiv/0 (mod 4) then there are no preferred pairs of binary m-sequences. The proof makes essential use of a deep theorem of McEliece (1971) that restricts the possible weights that can occur in a binary cyclic code.>