Irreducible Polynomials over Finite Fields

In summary: I'm not sure what you're asking. Is there a faster way to compute the resultant of two polynomials than just using the formulas 4.3 and 4.4? If so, please explain. No, I'm not sure what you're asking.
  • #1
burritoloco
83
0
Hi, yet another question regarding polynomials :). Just curious about this.

Let f(x), g(x) be irreducible polynomials over the finite field GF(q) with coprime degrees n, m resp. Let [itex]\alpha , \beta[/itex] be roots of f(x), g(x) resp. Then the roots of f(x), g(x), are [itex]\alpha^{q^i}, 0\leq i \leq n-1[/itex], and [itex]\beta^{q^j}, 0\leq j \leq m-1[/itex].

Question: What is the irreducible polynomial over GF(q) of degree nm with roots [itex]\alpha^{q^i}\beta^{q^j}[/itex] where [itex]0\leq i \leq n-1[/itex], and [itex]0\leq j \leq m-1[/itex]. Can you define such polynomial explicitly in terms of just f(x) and g(x) without the roots appearing in the formula?

Note: The last sentence/question is what really interests me as the following is the required polynomial (but defined in terms of the roots of f(x))

[tex]F(x) = \prod_{i=0}^{n-1}\alpha^{mq^i}g\left(\alpha^{-q^i}x\right)[/tex]

Thank you!
 
Last edited:
Physics news on Phys.org
  • #2
It depends somewhat on just what you mean by "formula" and "appearing in".

I know that F can be expressed as a resultant. The formula you give is presumably comes from one of the methods of computing resultants. There exist other ways to compute resultants, such as as the determinant of a matrix, or a Euclidean algorithm-like method.

You could always find a way to write down the system of equations that literally expresses that [itex]\alpha \beta[/itex] is a root of F(x). Then F would be the solution!
 
  • #3
I see. I was expecting some kind of miracle where F(x) could be expressed as some sort of polynomial compositions of f(x), g(x) and their reciprocals, but this matter turns out to be even more complicated than I was hoping. Here's a paper I have just found on this topic.

http://books.google.ca/books?hl=en&...XCGpX7oK3R2OU8ZHNYtuYkoZU#v=onepage&q&f=false

Theorem 4.2 says it all...
 
  • #4
Ah! The resultant formulas I was recalling are formulas 4.3 and 4.4. (Appearing just before theorem 4.3)
 
  • #5
Thanks Hurkyl. I'll probably be coming up with more questions as my project goes along :). Feel free to answer whenever you can, haha. Great to have Physics Forums around.
 
  • #6
Hmm, resultants and Thm 4.2 seem to be general methods on any two polynomials f(x), g(x) to obtain F(x). What if there are special classes of polynomials for which this computation could be done totally differently and much faster than the O(n^3 log^2(n)) in their paper? But what is this all good for anyways lol.
 

FAQ: Irreducible Polynomials over Finite Fields

What is an irreducible polynomial over a finite field?

An irreducible polynomial over a finite field is a polynomial that cannot be factored into lower degree polynomials over the same field. This means that it cannot be broken down into simpler terms and has no roots in the field.

Why are irreducible polynomials important in finite fields?

Irreducible polynomials are important in finite fields because they are the building blocks for constructing field extensions. They also play a crucial role in coding theory and cryptography, as they are used to generate finite field elements for coding and encryption algorithms.

How do you determine if a polynomial is irreducible over a finite field?

One method for determining if a polynomial is irreducible over a finite field is by using the Berlekamp's algorithm. This algorithm checks for the existence of non-trivial divisors of the polynomial by factoring it over a larger extension field. If no such divisors are found, then the polynomial is irreducible.

Can an irreducible polynomial over a finite field have multiple roots?

No, an irreducible polynomial over a finite field cannot have multiple roots. This is because if it did have multiple roots, then it would be divisible by the linear factors corresponding to those roots, contradicting its irreducibility.

Are there any patterns or properties of irreducible polynomials over finite fields?

Yes, there are several patterns and properties of irreducible polynomials over finite fields. For example, the number of irreducible polynomials of a given degree over a finite field is finite. Also, the degree of an irreducible polynomial must divide the size of the finite field. Additionally, there are specific constructions for generating irreducible polynomials over finite fields, such as the primitive polynomial construction.

Similar threads

I Finite fields, irreducible polynomial and minimal polynomial theorem
Replies
6
Views
2K
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
I Proving properties of polynomial in K[x]
Replies
8
Views
1K
MHB Can a Unique Polynomial Satisfy Specific Integral Equations?
Replies
4
Views
1K
I Splitting Fields: Anderson and Feil, Theorem 45.5 ....
Replies
9
Views
1K
MHB Splitting Fields: Anderson and Feil, Theorem 45.5
Replies
1
Views
1K
MHB Proof: K is a Root Field for Every Irreducible Polynomial with a Root in K
Replies
1
Views
1K
MHB How Does Polynomial Splitting Occur in Finite Field Extensions?
Replies
1
Views
1K
MHB How can we prove that E/Q is a normal extension?
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top