From: Bill Dubuque Newsgroups: sci.math,sci.crypt.research,sci.math.symbolic Subject: Re: Determining irreducible polynomial Date: 11 Nov 1996 22:40:50 -0800 pecampbe@mtu.edu (Paul E. Campbell) wrote: >I've been studying codes recently, which mostly tend to rely on using >extensions over the finite field GF(2). > >So, other than exhaustive checking or simply calling the libraries built into >Maple or Mathematica, how does one determine whether a polynomial is >irreducible? Is there a way to find an irreducible polynomial without >resorting to some sort of random or systematic search given a degree and >a field? The polynomial Q(X) in GF(p)[X] of degree n is irreducible iff n p X = X (mod Q(X)) and for all primes q dividing n n/q p gcd( X - X, Q(X) ) = 1. The proof is an easy exercise using only basic properties of finite fields. Using repeated squaring to computer powers, this gives an O(n^3*ln(p)) algorithm, assuming that the degree n is quickly factorizable -- which is always the case in current practice. Note that this practical polynomial irreducibility test is an analog of the impractical Pocklington-Lehmer integer primality test (e.g. see Section 3.4.3 of Cohen's text A Course in Computational Algebraic Number Theory). Special parameterized classes of irreducible polynomials are known in various cases, e.g. for classical results see Chapter V of A. Albert's text Fundamental Concepts of Higher Algebra (a most useful reference for classical results on Finite Fields). No doubt there are many new results given the recent intense applications of finite fields to cryptography, etc., e.g. see the Math Review below. -Bill Dubuque ------------------------------------------------------------------------------ 95m:11136 11T06 Niederreiter, Harald (A-OAW-I) An enumeration formula for certain irreducible polynomials with an application to the construction of irreducible polynomials over the binary field. (English. English summary) Appl. Algebra Engrg. Comm. Comput. 1 (1990), no. 2, 119--124. ------------------------------------------------------------------------------ The paper answers some questions posed by Meyn. The author obtains an explicit formula for the number of polynomials $f(x) = x\sp n + a\sb {n-1}x\sp {n-1} + \cdots + a\sb 1x + 1$ irreducible over ${\bold F}\sb 2[X]$ with $a\sb {n-1} = a\sb 1 = 1$. Such polynomials are called $A$-polynomials. In particular, it follows from that formula that such polynomials exist for all $n \ge 2$ with $n \ne 3$. The importance of such polynomials is provided by the following result. For a polynomial $F(X) \in {\bold F}\sb 2[X]$ of degree $d = \deg F$, define the $Q$-transform as follows: $F\sp Q(X) = x\sp d F(X + 1/X).$ If $f(X)$ is an $A$-polynomial then every term of the recursively defined sequence $f\sb 0(X) = f(X)$, $f\sb i(X) = f\sb {i-1}\sp Q(X)$ is irreducible over ${\bold F}\sb 2$. Reviewed by Igor E. Shparlinski