Irreducibility test for polynomials over Fp

  • Thread starter Thread starter geor
  • Start date Start date
  • Tags Tags
    Polynomials Test
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:

Thread '##(A/\mathfrak{a})_{\mathfrak{p}/\mathfrak{a}}## and its isomorphism?'

I asked online questions about Proposition 2.1.1: The answer I got is the following: I have some questions about the answer I got. When the person answering says: ##1.## Is the map ##\mathfrak{q}\mapsto \mathfrak{q} A _\mathfrak{p}## from ##A\setminus \mathfrak{p}\to A_\mathfrak{p}##? But I don't understand what the author meant for the rest of the sentence in mathematical notation: ##2.## In the next statement where the author says: How is ##A\to...
View full post »

Thread 'Questions about non existence of GCDs vs (coimages, cokernels)'

The following are taken from the two sources, 1) from this online page and the book An Introduction to Module Theory by: Ibrahim Assem, Flavio U. Coelho. In the Abelian Categories chapter in the module theory text on page 157, right after presenting IV.2.21 Definition, the authors states "Image and coimage may or may not exist, but if they do, then they are unique up to isomorphism (because so are kernels and cokernels). Also in the reference url page above, the authors present two...
View full post »

Thread 'Decomposition into irreps of compact Lie group'

When decomposing a representation ##\rho## of a finite group ##G## into irreducible representations, we can find the number of times the representation contains a particular irrep ##\rho_0## through the character inner product $$ \langle \chi, \chi_0\rangle = \frac{1}{|G|} \sum_{g\in G} \chi(g) \chi_0(g)^*$$ where ##\chi## and ##\chi_0## are the characters of ##\rho## and ##\rho_0##, respectively. Since all group elements in the same conjugacy class have the same characters, this may be...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top