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 calculate with $\mathbb{Z}/2\mathbb{Z}$ with an unknown variable?

When calculating with numbers from a $\mathbb{Z}/2\mathbb{Z}$ how do you deal with unknown variables? For example, if I have the following term: $(a - 1)(a - 1) - (a - 1) - (a - 1) = a^2 + 1$ Or is this incorrect?
Max
  • 255
0
votes
2 answers

Finding squares in finite fields

I need the definition of finding squares in finite fields and also the number of squares in a finite field. How can we find squares in $\Bbb F_5$ and $\Bbb F_7$? (Here $\Bbb F_5$ and $\Bbb F_7$ indicate the finite fields for $q=5$ and $q=7$…
juliet
  • 349
0
votes
1 answer

Let $C_i=\{i\cdot q^j \pmod{q^m-1}\, ||\, j=0,1,\cdots ,m-1\}$. If $\gcd(i,q^m-1)=1$, then $|C_i|=n$.

Let $$ C_i=\{i\cdot q^j \pmod{q^m-1}\, ||\, j=0,1,\cdots ,m-1\}. $$ My question: How to show that if $\gcd(i,q^m-1)=1$, then the cardinality of $C_i$, denoted with $|C_i|$, is equal to $m$. Thanks for any help.
user0410
  • 582
0
votes
2 answers

Representations of the formulas with the elements of the linear representations of $GF(2^2)$

The problem statement is as below. Represent the following formulas with the elements which are of the linear representations of $GF(2^2)$ where the root $\alpha$ satisfies $x^2+x+1=0$ . $(1)$ $\alpha^4$ $(2)$ $\alpha^2-(\alpha-1)$ $(3)$…
user802763
0
votes
1 answer

Understandig proof of a theorem on finite fields.

The theorem statement is: a finite field of characteristic $p$ has $p^n$ elements. I found this very simple proof in the book "Ling, San; Xing, Chaoping; Coding Theory - A First Course". But I don't understand the highlighted step. Doesn't that…
0
votes
1 answer

Do diagonal elements in the Galois Field addition tables have to be zeros?

I've seen addition and multiplication tables for Galois Fields, where the addition table is simply modular arithmetic, and some tables where the diagonal elements are zeros (i.e. the additive inverse of an element is itself). From what I can see,…
0
votes
1 answer

Degree of extension over finite fields with two elements having same degree irreducible

I get that Q(√2,√3) has degree 4 over Q. Now consider finite field F and a,b lying in an extension of F having same degree irreducible polynomial over F, let it be 'd'. Is the extension F(a,b), of degree d or d^2`? Like for example for d=2, whether…
0
votes
1 answer

What is the Galois Group of $x^4+1$ over $\mathbb{F}_3$ and describe the action of the group on the roots of it's polynomial

I know the Galois Group is cyclic of order 2 and I got the splitting field to be $\mathbb{F}_9$ but I don't understand how to write the frobenius automorphism that describes the action
0
votes
1 answer

Is it possible for Galois Field Multiplication result beyond the field

Consider $GF(2^8)$ with reducing polynomial $m_p = x^8+x^4+x^2+x^1+x^0$, compute multiplication between $a=x^7+x^0$ and $b=x$. Following https://en.wikipedia.org/wiki/Finite_field_arithmetic#Multiplication, it seems that the multiplication rule $a…
Chong
  • 103
0
votes
2 answers

The equation $x^2+y^2=0$ over finite fields

Do we have a fast method for proving that the equation $x^2+y^2=0$ over $\mathbb{F}_{7}$ has one solution $(0,0)$ without testing all the elements of $\mathbb{F}_{7}$?
olgaolgano
  • 55
  • 5
0
votes
0 answers

Construct a self-dual basis of $\Bbb F_{16}$ over $\Bbb F_2$

Help please. I don't understand how to do that, but I want to solve this problem. This problem is from "Introduction to finite fields and their applications" by Lidl and Niederreiter.
0
votes
0 answers

Does a finite field have to be a complete residue system, or could it be just a residue class?

Suppose $\mathbb{F}_3$ denotes the finite field $(F,\oplus,\odot)$, where $|F|=3$, and therefore $\oplus$ denotes addition modulo $3$, and $\odot$ denotes multiplication modulo $3$. Now, we wish to pick elements to fill the set $F$. We note that we…
0
votes
1 answer

Quadratic Gauss Sums to prove law of quadratic reciprocity

Suppose we have $g_{2} = \sum_{t=0}^{p-1} \omega^{t^{2}}$, where $\omega$ denotes the p^th root of unity, and p is a prime equivalent to $1 \pmod{4}$. Let $q$ be a prime equivalent to $1 \pmod{4}$. How do I show that $g_{2} \in \mathbb{F}_{q} \iff…
0
votes
0 answers

Approximating a Euclidean Algorithm

Given the problem of computing the GCD of two given elements over any finite field with characteristic 2. $$ r_1 = q_1r_2 + r_3 \\ r_2 = q_2r_3 + r_4 \\ r_3 = q_3r_4 + r_5 \\ \vdots \\ r_{k-1} = q_{k-1}r_{k} + r_{k+1}\\ r_k =…
juaninf
  • 1,264
0
votes
3 answers

Can a finite set with a non prime number of elements be a field?

I understand that as typically defined (using modular arithmetic) finite fields require a prime number of elements. But I recall hearing someone say that if you modify the way addition and multiplication is defined on a set with a non-prime number…
Snowball
  • 1,089