Studies On Irreducible Polynomials Over Finite Fields

Irreducible polynomials over finite fields play an important role in many applications of cryptography today.As the compute power grows,the existence and distribution of irreducible polynomials with higher degree is more of a practical problem.There are mainly three directions,one of which is on the distribution of the irreducible polynomials of a higher degree,another direction is on generating irreducible polynomials of a higher degree using composing method or other methods,the third direction is to search for irreducible polynomials of a higher degree with special attributes.Our research mainly deals with the first two directions,and is on the irreducible polynomials over the finite field GF(2).We first analyse the discrimination of a special class of irreducible polynomials,and prove a simpler formula,and prove a theorem on self reciprocal irreducible pentanomials.Then an algorithm on computing irreducible polynomials using Newton formula and an algorithm on generating necklaces is proposed in the article.Finally we deal with the iteration method of generating irreducible polynomials,and a new class of polynomials is posed as well.1.In order to determine whether a special kind of pentanomial is reducible or not,the discriminate of it should be checked,we prove a simplified formula that can be used in the computation procedure.We then prove a theorem to confirm that under the condition of the theorem,there is no self reciprocal irreducible pentanomials of the certain degree given in the theorem.By computer search,we give a conjecture on this topic.2.Using Newton formula and the theory of symmetric polynomials,we pose an algorithm to make the computation of the trace function faster,and the apply it on the computation of irreducible polynomials and primitive polynomials.As the necklaces are related to the problem of irreducible polynomials,we proposed an algorithm to generate necklaces,there are no non-necklaces in our algorithms.3.We then research on the composed method of generating irreducible polynomials of higher degrees,we prove under what condition can the generated polynomials be the same,we then use this to compute how many different polynomials can be generated.Finally,as the polynomial basis of an irreducible polynomial is of great importance for computing,especially the basis with less elements whose trace function equals 1,we give a new class of polynomial which suits these demands.