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 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