Irreducibility test for polynomials over Fp

geor

Hello everyone,
I need some help with this one:

I need to write a routine that tests
the irreducibility of a polynomial over Fp,
(where Fp is the finite field with p
elements and p is a prime).

It should take as input: p,the polynomial
and its degree.

It should return TRUE if the polynomial is
irreducible over Fp and FALSE if it's not.

I can use the theorem below:

The polynomial x^(p^n)-x is the product of
all monic irreduble polynomials over Fp,
of degree that divides n.

So, any ideas?
Thanks in advance for your time!

geor

Anything?..
Anybody?...

HallsofIvy

How large is p expected to be? With a computer, the brute force method of trying each integer, n, less than p to see if it makes the polynomial equal to 0 shouldn't be too bad.

geor

Well, it's more for the sake of the problem..
Mathematical languages like Maple, already have
routines for that.

matt grime

Well, use the theorem you were given - write a program to calculate gcds. If for example, you had to test a degree 5 poly, and you worked out the gcd with (x^p)^n - x, then what are the possible degrees of answers?

Remember, you don't need to find the factors, but just find the degrees of the irreducible factors.

Now, take the example above. Suppose n=>5. If f has degree 5, and gcd(x^p^n - x,f) =f, then what does this tell you about the degrees of the factors of f? Well, they must divide n, and sum to 5. What choice of n would be good to give you information?

I'm trying to find a way to prod you in the right direction, but it's hard because it seems obvious to me what you need to do, and I can't find the hint that doesn't just give it away straight away. Surely it should be clear from the fact that you've been given that theorem, that you should test a poly by taking lots of gcds. So just think about how knowing gcds gives you info about the degrees of the factors of f.