On The Coefficients Of Primitive Normal Polynomials

In this dissertation, we investigate the distribution of primitive normal polynomials over finite fields with the help of estimates of character sums over Galois rings and the p-adic method. The primitive normal Hansen-Mullen conjecture is proposed, and is finally established for n≥9, i.e., for any integer n≥9 and q a prime power, there exists a primitive normal polynomial with any specified coefficient arbitrarily prescribed.Primitive normal elements and primitive normal polynomials over finite fields play an important role in cryptography, especially the fast implementation of public key cryptosystem. The distribution of primitive normal polynomials, which was widely discussed, has great theoretical significance in many applications such as cryptography for doing computation efficiently in finite fields, fast Fourier transform algorithm and error-correcting code theory, etc.To solve the primitive normal Hansen-Mullen conjecture, we first translate the existence of primitive normal polynomial over finite fields with a coefficient prescribed into the existence of primitive normal element solutions of some system of trace equations over Galois rings by using the p-adic analysis method. To remove the restriction that the reciprocal polynomial of a primitive normal polynomial may not be a primitive normal polynomial, a kind of trace equation with variable x-1 is introduced to give a new problem reduction, so that the existence of primitive normal polynomials with any one of the last half coefficient prescribed can be established. On the other hand, the z-criterion is used to give another new problem reduction so that the estimate of the number of primitive normal element solutions of the system of trace equations can be improved by O(q1/2).Then we give some sufficient conditions to investigate whether the primitive normal Hansen-Mullen conjecture holds by estimates of character sums over Galois rings and Cohen's sieve techniques. Furthermore, a new variation of Cohen's sieve technique which acts both on qn– 1 and xn– 1 is introduced to make the computation easier and to cover more cases of small n. Lastly we consider the four cases q > n≥15, 9≤n≤14 and q > 101, 16≤q≤n, q < 16 respectively. We give a detailed study on the numbers of prime factors of integers and the irreducible factors of polynomials, and then reduce the possible exceptions into a small search scope that can be achieved by a computer with the help of some computing techniques. Finally, we get the following result.Theorem:Assume that n≥9. Then for any prime power q, any positive integer 1≤m < n and any element a∈Fq, there exists a primitive normal polynomial f (x) = xn -σ1x^n-1 +···+ (-1)n-1σn-1x + (-1)nσn withσm = a, except that (m, a) = (1, 0).