Irreducible Polynomials over Finite Fields


by burritoloco
Tags: fields, finite, irreducible, polynomials
burritoloco
burritoloco is offline
#1
Jun15-11, 04:06 PM
P: 85
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!
Phys.Org News Partner Science news on Phys.org
Internet co-creator Cerf debunks 'myth' that US runs it
Astronomical forensics uncover planetary disks in Hubble archive
Solar-powered two-seat Sunseeker airplane has progress report
Hurkyl
Hurkyl is offline
#2
Jun15-11, 05:49 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101
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!
burritoloco
burritoloco is offline
#3
Jun15-11, 06:15 PM
P: 85
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&l...page&q&f=false

Theorem 4.2 says it all...

Hurkyl
Hurkyl is offline
#4
Jun15-11, 06:25 PM
Emeritus
Sci Advisor
PF Gold
Hurkyl's Avatar
P: 16,101

Irreducible Polynomials over Finite Fields


Ah! The resultant formulas I was recalling are formulas 4.3 and 4.4. (Appearing just before theorem 4.3)
burritoloco
burritoloco is offline
#5
Jun15-11, 07:02 PM
P: 85
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.
burritoloco
burritoloco is offline
#6
Jun15-11, 08:21 PM
P: 85
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.


Register to reply

Related Discussions
Fast Construction of Irreducible Polynomials of degree n over any Finite Field Linear & Abstract Algebra 1
Fast Construction of Irreducible Polynomials of degree n over any Finite Field General Math 1
Modern Algebra: Fields/Polynomials/Irreducible Calculus & Beyond Homework 0
Finite fields and products of polynomials Calculus & Beyond Homework 0
Irreducible polynomials over finite fields Linear & Abstract Algebra 15