From: cet1@cus.cam.ac.uk (Chris Thompson)
Newsgroups: sci.math
Subject: Re: Polynomials in finite fields.
Date: 9 Feb 1996 16:03:31 GMT

In article <3118B35C.1187@stud.umist.ac.uk>, Andrew Braithwaite <A.J.Braithwaite@stud.umist.ac.uk> writes:
|> I have posted this problem once but I lost all my replies due to a mail 
|> server problem.
|> 
|> Im writing a program to test the irreducibility of polynomials in Zp (p 
|> a prime) the field of integers modulo p.
|> 
|> I know that the product of all the irreducible primes of degree r is 
|> x^(p^r)+x (call it q(x)).

As Timothy Murphy, has already pointed out, that should be x^(p^r)-x
being the product of all irreducible polynomials with degree dividing r.
 
|> I can test the irreducibilty of f(x) by finding the hcf(f(x),q(x)) and 
|> testing whether it is 1 for all 1<=r<=[n/2] (n is the degree of f(x)).
|> 
|> I know there is a better way of doing this which involves a polynomial 
|> with degree a lot lower than that of q(x). I would be very grateful for 
|> any pointers people could send me.

First: there is no need to make that big a meal of the large degree of
q(x). You compute at all stages modulo f(x), successively raising 
x^(p^r) mod f(x) to the p'th power (by O(log p) multiplications and
reductions mod f(x)), and you never have to work with polynomials of 
degree much larger than n.

But secondly: yes, there is a cheaper way of determining whether f(x)
is irreducible or not, if you don't care about the factors in the latter
case. This is the first part of Berlekamp's algorithm (see [1] or [2]):

First make sure f(x) is square-free by computing gcd(f(x),f'(x)). Then
compute x^(kp) mod f(x) for 0<=k<n, and consider the nxn matrix Q of
coefficients in Z_p that results. f(x) is irreducible iff Q-I has rank 
n-1 (more generally, Q-I has rank n-r if f(x) has r factors). As Z_p is
a field, this can be determined by the usual linear algebra algorithms.

When using Berlekamp's algorithm to do full factorisation, you don't in
fact have to the preliminary splitting into distinct degree factors by
finding gcd(x^(p^r)-x,f(x)) if you don't want to. Berlekamp's algorithm
has (notoriously) an \Omega(p) step in it, but you can restore polynomiality
in n and (log p) by borrowing ideas from Cantor-Zassenhaus (converting
from  a deterministic to a random algorithm) - see [2] Algorithm 3.4.11.

[1] Donald E. Knuth
    The Art of Computer Programming, Volume 2 - Seminumerical Algoithms
    Addison-Wesley (1981) [2nd edition] ISBN 0-201-03822-6
    (section 4.6.2)

[2] Henri Cohen
    A Course in Computational Algebraic Number Theory
    Springer (1993) ISBN 0-387-55640-0
    (section 3.4)

Chris Thompson
Email: cet1@cam.ac.uk