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