Questions tagged [finite-fields]

Finite fields are fields (number systems with addition, subtraction, multiplication, and division) with only finitely many elements. They arise in abstract algebra, number theory, and cryptography. The order of a finite field is always a prime power, and for each prime power $q$ there is a single isomorphism type. It is usually denoted by $\mathbb{F}_q$ or $\operatorname{GF}(q)$.

The order of a finite field is always a prime power, and for each prime power $q = p^r$ with $p$ prime there is a single isomorphism type. It is usually denoted by $\mathbb{F}_q$ or $\operatorname{GF}(q)$. The finite field $\mathbb F_q$ has characteristic $p$.

In the case $r = 1$ (i.e. $q = p$), a representative of $\mathbb F_p$ is given by the ring $\mathbb{Z}/p\mathbb{Z}$ of integers residue classes modulo $p$. For $r \geq 2$, $\mathbb F_q$ can be constructed by a quotient ring $\mathbb{F}_p[x]/\langle f(x)\rangle$, where $f\in\mathbb F_p[x]$ is an irreducible polynomial of degree $r$.


Questions about finite fields typically fall into one of the following groups:

1: Questions arising in introductory level courses on abstract algebra. Here abstract-algebra is a suitable related tag.

2: Questions about solvability of higher degree congruences and/or factorization of polynomials with integer coefficients modulo a prime number often need basic facts about finite fields. This kind of questions are adequately tagged with polynomials and/or elementary-number-theory. Adding a finite-fields tag may help, but may not be necessary to attract quality answers.

3: Finite fields naturally occur in algebraic-number-theory as their properties are used heavily in the study of prime ideals and their behavior under field extensions. Use the tags jointly, if you see the need for it. A rich area in the intersection of finite fields and number theory is that of characters, most notably character sums. For the latter exponential-sums is an appropriate auxiliary tag.

4: Many error-correcting codes use a finite-field as the alphabet representing data, and such codes depend heavily on the properties of the alphabet fields. Use the coding-theory tag in conjunction with finite-fields, if your question is under this umbrella. Another rich source of applications of finite fields is cryptography.

5: There are special questions considering algebraic varieties and/or algebraic groups over finite fields. Here my recommendation is to use algebraic-geometry or algebraic-groups as the primary tag, and finite-fields as an auxiliary tag. This way your question will most likely attract the attention of those members who are best placed to answer it.


WARNING1: A relatively common mistake is to assume that finite-fields is an appropriate tag for questions about finite field extensions. There the word 'finite' is an attribute of the word 'extension' meaning that the dimension of the larger field as a vector space over the smaller one is finite. If that is what your question is about, you should use some combination of the tags galois-theory, field-theory, extension-field.


WARNING2: Another common source of confusion is the following. It is a well-known fact that a finite subgroup of the multiplicative group of any field is cyclic. Thus the entire multiplicative group of a finite field is cyclic. Any generator $g\in\Bbb{F}_q^*$ of the multiplicative group is called a primitive element. This is a natural extension of the concept of a primitive root in the multiplicative group $\Bbb{Z}/p\Bbb{Z}^*$ of the residue class ring. Unfortunately it is in conflict with the common practice of general field theory to call an element $z\in L$ primitive (w.r.t. the field extension $K/L$), if $L=K(z)$. In the case of finite fields we require more from a primitive element.

An irreducible polynomial $m(x)\in\Bbb{F}_p$ of degree $r$, is called a primitive polynomial, if any (and hence all) of its zeros in $\Bbb{F}_q$ are primitive elements. IOW, primitive polynomials are exactly the minimal polynomials (over the prime field) of primitive elements. This is another unfortunate source of confusion, for in the theory of polynomials over PIDs a polynomial is called primitive, if its coefficients have no non-unital common divisors. This is rarely very confusing for over a field this alternative concept of primitivity is patently meaningless.

Primitive polynomials are extremely useful in software implementations of the arithmetic of a moderate size finite field. This is largely because having a primitive polynomial at hand allows one to generate look-up-tables for both the base $g$ discrete logarithm as well as its inverse function. See this CW question for examples.

For that reason extensive tables of primitive polynomials have been generated. One such table is here.


Learn more: The tome for the keen students of finite fields is the book by Rudolf Lidl and Harald Niederreiter.

5331 questions
0
votes
3 answers

How to find order of all the elements in GF(19) and indicate those which are primitive elements?

As the GF(19) gets pretty lengthy by just writing each element in terms of each element powers, is there any other method to solve this?
0
votes
1 answer

To obtain the elementary symmetric polynomial in the binary finite field

Let $a$ be an element of order $n$ in $GF(2^q)$. Let $b$ be a non-zero element of $GF(2^q)$ such that $b\not \in \{r,r^2,\cdots ,r^n\}$. Assume that $x_i=(1+ba^i)$ for $1\leq i \leq n$. Now consider the elementary symmetric polynomial of degree…
Amin235
  • 1,867
0
votes
2 answers

performing division and multiplication over GF(p)

Considering a simple example: $$\frac{5x^2}{3x}\ \ \ \ \ over\ GF(7)$$ one way to do it would be: $$\frac{5}{3} x$$ $$\Rightarrow 5 \times 3^{-1}x$$ $$\Rightarrow 4x$$ But, I tried performing long division performing long division goes like…
0
votes
1 answer

If $[K:F] = 3$, show a non square in $F$ is a non square in $K$

Let $F \subset K$ be finite fields with $[K:F] = 3$. Show that if $\alpha \in F$ is not a square in $F$, it is not a square in $K$. My attempt: $[K:F] = 3 \implies \forall x \in K$, $x = \beta_1a_1 + \beta_2a_2+\beta_3a_3$, where $\beta_1, \beta_2,…
mlimber
  • 47
0
votes
0 answers

Algorithm for multiplication in finite field

I am trying to understand multiplication in finite fields. I have understood the usual multiplication method for multiplying two polynomials in a finite field. But I am unable to understand the algorithm using arrays, a portion of which from the…
SAK
  • 529
0
votes
2 answers

Field projection

I need a projection from $\mathbb{F}_{2^{n}}$ to $\mathbb{F}_{2^{n-1}}$. I was thinking in a projection of vector spaces, but i want to know if there is a "canonical" projection or something like that, because tha will be very helpful. Maybe i…
Dimitri
  • 1,939
0
votes
3 answers

Possible sizes of finite fields and the relation to the characteristic of the field

In my abstract algebra class we discussed the idea that for a finite field $F$, that the characteristic of $F$ is a prime number. The proof would go more or less like : Suppose that $char(F) = nm$ for $n,m \in \Bbb Z$ and $n,m \geq 2$.…
0
votes
1 answer

Help with a basic question on Finite Field characteristic

Let $F$ be a field of characteristic $p > 0$. Show that $(\alpha + \beta)^{p^m} = \alpha^{p^m}+\beta^{p^m}$, for all $\alpha,\beta \in F$ and $m > 0$. I am stuck on this question; can anybody help?
user625094
0
votes
0 answers

For each $k = 0, \dots, 26$ count the number of ordered pairs $(a,b)$ in $\mathbb{F}_{27} ^2$ for which $a^k = b^2$

I believe we have to check all values of $k$. $k = 0$: $a^0 = 1 = b^2$. This holds for all $a\in \mathbb{F}_{27}$, so we just have to find all $b \in \mathbb{F}_{27}$ for which $b^2 \equiv 1 \text{ (mod } 3)$. For $b \not\equiv 0 \text{ (mod } 3)$…
MyWorld
  • 2,398
0
votes
2 answers

Commutative Algebra over a Finite Field

Let $A$ be a commutative algebra over the finite field $\mathbb F_q$, of order $q$, where $q=p^l$, for a prime $p$ and a positive inteher $l$. Assume that $A$ is finite-dimensional. So, $A$ is a finite ring. Hence, we have the…
zacarias
  • 3,158
0
votes
0 answers

Relation between finite fields $F_{p^2}$ and $F_p(\omega)$.

Let $F_p$ be a finite field having $p$ elements(for some prime $p$), not having primitive $3$rd root of unit say $\omega.$ Then can i say that field $F_p(\omega)$ and $F_{p^2}$ are isomorphic. I tried as follows: As both of fields $F_{p^{2}}$ and…
neelkanth
  • 6,048
  • 2
  • 30
  • 71
0
votes
1 answer

Divisibility of polynomials in finite fields

Is the following known (or even correct)? Let $q = p^n$ be a prime power. Let $f(x), g(x) \in F_q[x]$ with $f(x) = x^m + ax^r + b$ with $a,b \ne 0$ and $g(x) = x^{mt} + cx^{rt} + d$ with $c,d \ne 0$ such that $f|g$ Then $t = p^i$ for some $i \ge 0$…
Dan
  • 64
0
votes
1 answer

Number of generator in the finite field

Our material defines generator like below. Sometimes it is easier to define the elements of the $GF(2^n)$ field using a generator. $\{0,g,g,g^2,...,g^N\}$, where $N=2^n-2$ But I cannot understand why $N=2^n-2$ not $2^n-1$. If $n=3$, $GF(2^3)$…
baeharam
  • 203
0
votes
1 answer

Why $\Bbb Z_{p}[x]$ is finite field?

I'm learning cryptography and today I learned Galoi's Field, but I cannot understand why $\Bbb Z_p[x]$ is finite field. I know $\Bbb Z_p$ is finite filed because $p$ is prime number and by EEA, but $Z_p[x]$ has too many polynomials which degree is…
baeharam
  • 203
0
votes
1 answer

Irreducible Polynomials over Finite Prime Fields

Is there a site that has tables of irreducible polynomials over Finite prime fields? Preferably up to at least degree 10 for primes 2, 3, and 5. Also, what programming language is helpful in factoring polynomials over finite fields?