Roots of polynomials over GF(p)

In summary, the conversation discusses the relationship between fields of characteristic p, roots of polynomials over the prime subfield GF(p), and the operation of taking powers in a finite field. It is important to note that this relationship only holds for elements in the prime subfield and not for elements outside of it. The conversation also mentions some relevant results in the text, such as the Mobius inversion formula and a formula for finding the number of irreducible polynomials over a finite field.
  • #1
joeblow
71
0
If F is a field of characteristic p, with prime subfield K = GF(p) and u in F is a root of f(x) (over K), then [itex]u^p[/itex] is a root of f(x).

Now, I know that [itex] x^p \equiv x (\text{mod } p)[/itex], so isn't it immediately true that [itex] f(x^p)=f(x) [/itex] (over K)? So, [itex] 0=f(u)=f(u^p) [/itex].

I only ask because this type of problem (as I understand it) is much more elementary than the material that the text is covering. In the section from which this problem comes, the main results are (1) that if F = GF(q), then the irreducible factors of [itex]x^{q^{m}}-x[/itex] over F are precisely the irreducible polynomials over F of degree dividing m, (2) the Mobius inversion formula, and (3) a formula for finding the number of monic irreducible polynomials of degree m over GF(q).

Please tell me if there is some critical misunderstanding that I am having.
 
Physics news on Phys.org
  • #2
In general, we don't have f(u)=f(up) in your field F, but only for u in K, and you also need to use that (a+b)p=ap+bp for any a,b in F. Then it should be easy and fun to write out 0=f(u)p and see where that leads.
 
  • #3
The result that [itex](a+b)^p=a^p+b^p[/itex] (which is all that is needed) was demonstrated (via exercise) much earlier in the chapter, though. Something is strange about the placement of this problem.
 
  • #4
It is true that, for every element [itex]a[/itex] of GF(p), we have [itex]a^p = a[/itex]. As a consequence, it's also true that, for every integer [itex]n[/itex], we have [itex]n^p \equiv n \pmod p[/itex]. Also as a consequence, for every polynomial with coefficients from GF(p) and element [itex]a[/itex] of GF(p), we have [itex]f(a) = f(a^p)[/itex]. Similarly, for every polynomial with integer coefficients and any integer [itex]n[/itex], we have [itex]f(n^p) \equiv f(n) \pmod p[/itex].

(Yes, I mean = where I've written =, and [itex]\equiv[/itex] where I've written [itex]\equiv[/itex])If [itex]x[/itex] is an indeterminate over GF(p), then it's not true that [itex]x^p = x[/itex]. Consequently, if [itex]t[/itex] is an indeterminate over Z, it's not true that [itex]t^p \equiv t \pmod p[/itex].

(While [itex]x[/itex] and [itex]x^p[/itex] both determine the same function on GF(p), they are different polynomials. And, e.g., they give different functions on GF([itex]p^2[/itex]))If [itex]u \notin \text{GF}(p)[/itex], then we have no reason to expect [itex]u^p = u[/itex]. If [itex]u[/itex] is not an integer, we have no reason to expect [itex]u^p \equiv p \pmod p[/itex] (if that equation even makes sense).For a finite field [itex]\text{GF}(p^e)[/itex], the operation [itex]a \mapsto a^p[/itex] is actually generalization of the idea of conjugation. For the special case of [itex]e = 2[/itex], you even have that [itex](a^p)^p = a[/itex]. (for larger [itex]e[/itex], you have to iterate [itex]e[/itex] times rather than just twice)
 
  • #5


I can understand your confusion and I am happy to clarify this concept for you. The statement "if u is a root of f(x) over K, then u^p is a root of f(x)" is a fundamental property of finite fields and polynomials over them. This property is known as the Frobenius automorphism and it is a key tool in understanding the structure of finite fields and their roots.

To understand why this property holds, we need to first understand the structure of finite fields. A finite field of characteristic p, denoted GF(p), is a field that contains p elements. The elements of GF(p) can be represented as integers from 0 to p-1, and arithmetic operations are performed modulo p. For example, in GF(5), the elements are 0, 1, 2, 3, and 4, and the addition and multiplication operations are performed modulo 5.

Now, let's consider a polynomial f(x) over GF(p). This polynomial can be written as f(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n, where a_i are elements of GF(p). When we raise this polynomial to the pth power, we get f(x)^p = (a_0 + a_1x + a_2x^2 + ... + a_nx^n)^p. By the binomial theorem, we can expand this polynomial as f(x)^p = a_0^p + a_1^px^p + a_2^px^2p + ... + a_n^px^{np}. Since we are working in GF(p), the pth power of any element is equal to itself (as you mentioned, x^p ≡ x (mod p)). Therefore, we can rewrite f(x)^p as f(x)^p = a_0 + a_1x^p + a_2x^{2p} + ... + a_nx^{np}. This is equivalent to f(x) (since we are working in GF(p), all the exponents are reduced modulo p). Hence, f(x)^p = f(x) over GF(p).

Now, let's go back to the statement "if u is a root of f(x) over K, then u^p is a root of f(x)". Since f(x)^p = f(x) over
 

1. What are the roots of a polynomial over GF(p)?

The roots of a polynomial over GF(p) are the values of x that make the polynomial equal to 0. In other words, they are the solutions to the polynomial equation in the finite field GF(p).

2. How do you find the roots of a polynomial over GF(p)?

To find the roots of a polynomial over GF(p), you can use the finite field version of the quadratic formula or other numerical methods such as trial and error. Additionally, you can use the discrete logarithm algorithm to find the roots.

3. How do the roots of a polynomial over GF(p) differ from the roots in a traditional polynomial?

The main difference is that the roots of a polynomial over GF(p) are limited to values within the finite field GF(p), whereas the roots of a traditional polynomial can take on any real or complex value. Additionally, the number of roots for a polynomial over GF(p) is limited to the degree of the polynomial, whereas a traditional polynomial can have an infinite number of roots.

4. Can a polynomial over GF(p) have multiple roots?

Yes, a polynomial over GF(p) can have multiple roots. However, the number of roots is always less than or equal to the degree of the polynomial. If a polynomial has multiple roots, it is said to be reducible over GF(p).

5. What is the significance of studying the roots of polynomials over GF(p)?

Studying the roots of polynomials over GF(p) has many practical applications in cryptography, coding theory, and error-correcting codes. It also has connections to other areas of mathematics such as number theory and algebraic geometry. Understanding the properties and behavior of these roots is crucial in solving problems and developing new algorithms in these fields.

Similar threads

  • Linear and Abstract Algebra
Replies
3
Views
706
Replies
6
Views
2K
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
Replies
8
Views
1K
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
888
Back
Top