From: Bill Dubuque <wgd@martigny.ai.mit.edu>
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