Irreducibility test for polynomials over Fp

  • Context: Graduate 
  • Thread starter Thread starter geor
  • Start date Start date
  • Tags Tags
    Polynomials Test
Click For Summary

Discussion Overview

The discussion revolves around developing a routine to test the irreducibility of a polynomial over the finite field Fp, where p is a prime number. Participants explore methods and theorems related to polynomial factorization and irreducibility, focusing on computational approaches and theoretical underpinnings.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Homework-related

Main Points Raised

  • One participant requests assistance in writing a routine to test polynomial irreducibility over Fp, mentioning the theorem that relates the polynomial x^(p^n)-x to monic irreducible polynomials.
  • Another participant suggests using a brute force method to evaluate the polynomial by testing integers less than p to see if they yield zero.
  • A different participant notes that mathematical software like Maple already has routines for testing irreducibility, implying that the problem may be more theoretical than practical.
  • One participant proposes using the gcd (greatest common divisor) method to determine the degrees of irreducible factors, emphasizing the importance of understanding how gcds relate to polynomial degrees.
  • Further elaboration is provided on how the degrees of factors must divide n and sum to the degree of the polynomial being tested, encouraging exploration of gcds for insights.

Areas of Agreement / Disagreement

Participants express varying levels of familiarity with the problem and potential methods, but there is no consensus on a single approach. Some suggest computational methods while others emphasize theoretical aspects, indicating multiple competing views on how to proceed.

Contextual Notes

The discussion does not resolve the specific computational challenges or assumptions regarding the size of p or the degree of the polynomial. There are also unresolved mathematical steps related to the gcd method and its implications for irreducibility testing.

geor
Messages
35
Reaction score
0
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:
Physics news on Phys.org
Anything?..
Anybody?...
 
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.
 
Well, it's more for the sake of the problem..
Mathematical languages like Maple, already have
routines for that.
 
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:

Similar threads

Undergrad Irreducible polynomials and prime elements
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad How to show ##p(x)=g(x)x\pm 1\in\Bbb{Q}[x]## is irreducible in ##\Bbb{Q}_{\Bbb{Z}}[x]##?
  • · Replies 48 ·
2
Replies
48
Views
6K
Undergrad Finite fields, irreducible polynomial and minimal polynomial theorem
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Looking for a creative or quick method for finding roots in GF(p^n)
  • · Replies 3 ·
Replies
3
Views
2K
MHB The polynomial is irreducible over Q(i)
  • · Replies 16 ·
Replies
16
Views
4K
MHB The irreducible polynomial is not separable
  • · Replies 1 ·
Replies
1
Views
3K
MHB Prove that there are infinitely many irreducible polynomials in Z5.
  • · Replies 3 ·
Replies
3
Views
4K
Undergrad What Conditions Ensure the Minimal Polynomial of α Divides P in Galois Theory?
  • · Replies 12 ·
Replies
12
Views
4K
Undergrad Confused about Gauss's Lemma of Irreducibility
  • · Replies 4 ·
Replies
4
Views
4K
Undergrad Splitting Fields: Anderson and Feil, Theorem 45.5 ....
  • · Replies 9 ·
Replies
9
Views
2K