Irreducible polynomials over finite fields

In summary: But we could construct a polynomial g of degree 5 such that [g(x):G]=5.Okay, so we can find a polynomial g such that [g(x):G]=5. But what does that prove? That g is the minimal polynomial of degree 5.I don't see how that helps us.
  • #1
gonzo
277
0
Can someone explain to me why the following is true (ie, show me the proof, or at least give me a link to one):

Over the field Zq the following polynomial:

x^q^n-x

is the product of all irreducible polynomials whose degree divides n


Thanks.
 
Physics news on Phys.org
  • #2
Somethings not quite right in the statement i think. First of all, i guess the q is prime. Secondly, do you mean over the field GF(q^n) and not Z_q ?

[edit]Now that i think about it, you did mean Z_q. Let me call it F_q rather.
The proof of this is carried out over some steps.

1. Lemma : If f belongs F_q[x] is an irreducible polynomial over F_q of degree m (say), then f(x) would divide x^q^n - x iff m divides n
This would imply that all monic irreducible polynomials over F_q that we see in the factorization of x^q^n-x (belonging to F_q[x]) are exactly those whose degree divides n

2. Lemma : An f belonging to F_q[x] has a multiple root iff (f,f') != 1
Now Consider g(x) = x^q^n-x. So g'(x) = -1. So from the above lemma, we get that all monic irreducible polynomials whose degree divides n, occur exactly once in factorization of g in F_q[x]

Hence proved.
I have avoided proofs of the above lemmas. I guess they should be simple enough to be proved.[/edit]

-- AI
 
Last edited:
  • #3
Thanks, but could you please show me the proof for lemma 1? And yes, q has to be prime, sorry for not stating that, I thought it was implied since I said Zq was a field.
 
  • #4
well the roots of that polynomial form a field extension of Fq, of degree n, hence their minimal polynomials are all factros of that polyno9mial. isn't that about it?
 
  • #5
oh and just because Fq is a field, it does not of course follow that q is prime, unless you think that Fq means Z/qZ.

usually Fq denotes the unique field of order q where q is a power of a prime p.
 
  • #6
Lemma 1 : If f belongs F_q[x] is an irreducible polynomial over F_q of degree m (say), then f(x) would divide x^q^n - x iff m divides n

Proof :
First half -->
Let k be a root of f(x)
F_q(k) is a subfield of F_q^n (why??)
[F_q(k):F_q] = m
but [F_q^n : F_q] = n
Therefore, m divides n (why??)

Converse,
given m|n
F_q^m is a subfield of F_q^n (why??)

If k is a root of f,
then F_q(k) = F_q^m (why??)

Therefore, k is a root of x^q^n - x (why??)
Hence, f divides x^q^n - x

I have left a lot of details in the proof, try to fill them in.

-- AI
 
  • #7
Hi everyone. I have a question: How can we show that an element s of order q^n -1 belonging to GL(n,q) has a minimal polynomial of degree n? Or equivalently that it's characteristic polynomial is irreducible?
 
  • #8
Resurrecting dead threads isn't usually a good idea.

But to answer your question...

What are the definitions of all the things involved? Let's write them out.

1) What is the definition of min poly?

2) Suppose that f is reducible: f(x)=g(x)h(x) and that a is a root of f, i.e. f(a)=0.

3) Does that imply anything about g(a) or h(a)?

4) Remember this is a field
 
  • #9
Sorry about that. I realized it was a dead thread after I posted. To answer 2) it would imply that a would either be a root of g(x) or h(x). But I still don't see how that would give us the irreducibility of the characteristic polynomial.
 
  • #10
So, if it's a root of a poly of smaller degree, wouldn't that negate some part of the definition of _minimal_ (I think I mistakenly used characteristic in the last post) polynomial?
 
  • #11
If you use the minimal polynomial, then what we need to show is that it's degree is n. I simply said that this is equivalent to showing that the characteristic polynomial is irreducible (that's because the minimal polynomial is irreducible and divides the characteristic polynomial). I will make the question more specific: Take GL(5,2)
and the element [01110]
[00011]
[00111]
[11000]
[01000]
which is of order 31. It's minimal polynomial is x^5 + x^4 + x^3 + x^2 + 1. How can we assure that it's degree is 5 without evaluating it. It could as easily be 2 or 3 or whatever.
 
  • #12
Ah, got you. Not having a good time with my return to this kind of mathematics.
 
  • #13
Well, the obvious observation is that if [itex]a[/itex]'s char poly is reducible, then it implies that [itex]a[/itex] lies in a proper subfield of F_{q^n}, i.e. the splitting field of the char poly is not F_{q^n}. But I'm not seeing a way to write that in a way that doesn't just say 'nah, because it is'.
 
  • #14
I suppose the more formal proof goes along the lines of:

the roots of a poly of degree k form a subfield of degree q^k, and hence any element has order at most q^k-1, if k is not n, then this is a contradiction.
 
  • #15
If z is an element of order p^n-1 in GF(p^n), it is the generator of the cyclic multiplicative group, and by the Primitive element theorem, GF(p^n) = Zp[z]. Therefore it's irr. polynomial is of degree n.
 
  • #16
I mean Zp(z), the field, of course.

Steve
 

1. What are irreducible polynomials over finite fields?

Irreducible polynomials over finite fields are polynomials that cannot be factored into smaller polynomials over a finite field. They are often used in cryptography and coding theory.

2. How are irreducible polynomials over finite fields different from irreducible polynomials over real numbers?

The key difference is that over finite fields, the number of possible coefficients and exponents are limited, whereas over real numbers, they are infinite. This affects the properties and behavior of irreducible polynomials.

3. Why are irreducible polynomials over finite fields important in cryptography?

Irreducible polynomials are used in cryptography to generate finite fields, which are essential for many encryption and decryption algorithms. They also provide a way to securely represent and manipulate data in a finite amount of space.

4. How can one determine if a polynomial is irreducible over a finite field?

One method is to check if the polynomial has any roots in the finite field. If it does not, then it is irreducible. Another method is to use various algorithms, such as the Berlekamp algorithm, to test for irreducibility.

5. Can irreducible polynomials over finite fields be used for error correction in data transmission?

Yes, they can be used in error correction codes, such as Reed-Solomon codes, to detect and correct errors in transmitted data. This is because they have desirable properties that make them suitable for this purpose, such as being able to detect and correct multiple errors.

Similar threads

Replies
6
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
718
  • Linear and Abstract Algebra
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
12
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
2K
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
3K
Back
Top