Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Irreducibility test for polynomials over Fp

  1. Sep 7, 2007 #1
    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!
    Last edited: Sep 7, 2007
  2. jcsd
  3. Sep 8, 2007 #2
  4. Sep 8, 2007 #3


    User Avatar
    Science Advisor

    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.
  5. Sep 9, 2007 #4
    Well, it's more for the sake of the problem..
    Mathematical languages like Maple, already have
    routines for that.
  6. Sep 9, 2007 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
    Last edited: Sep 9, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook