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
3
votes
2 answers

Uncountability of $\overline{\mathbb{F}_p}$.

In the following MathOverflow question, it has been pointed out that $\overline{\mathbb{F}_p}$ is an uncountable set. Whereas according to http://press.princeton.edu/chapters/s9103.pdf (see page 4 theorem 1.2.1) the closure $\overline{\mathbb{F}_p}$…
3
votes
2 answers

Solutions of affine polynomials in characteristic $2$

I will give an example for expressing where I stuck about affine polynomials: Let $\alpha \in \mathbb F_{2^k}^*$. Let $L_{\alpha}(x)=x^4+x^2+\alpha x$ be a linearized polynomial over $\mathbb F_{2^n}$ with $k \mid n$. What is $\{x \in \mathbb…
vudu vucu
  • 1,040
3
votes
1 answer

Notation: graphs representing relations between fields

What are these things called? Can someone explain what the undirected edges represent? Example Diagram 1 Definitions: $F_{4096}$, $F_{64}$, $F_{16}$, $F_8$, $F_4$, and $\mathbb{Z}/2\mathbb{Z}$ are all finite fields. Example Diagram…
Snowball
  • 3,078
  • 18
  • 37
3
votes
2 answers

Does this equation in $\mathbb{Z}_p$ always have a solution?

Is there always a solution to the equation in the field $\mathbb{Z}_p$ ($p$ being a prime number) $$ a^2 + b^2 \equiv c \pmod p $$ for a given $c \in \mathbb{Z}_p$? The solution need not be unique, I only want to know if there exist such $a, b \in…
Nerius
  • 159
3
votes
3 answers

How to find all of generators in a finite fields

How can I find all generators of a finite field? For example in GF(2^3) and X^3 + x^2 + 1 as primitive polynomial. I don`t want all of solutions. I need some hint and help to solve this problem. Thanks a lot. Ya Ali.
2
votes
2 answers

Connecting the $+$ with the $\cdot$ operation in a field $(F,+,\cdot)$

I have to prove that the product of all invertible elements in a finite field,$F^*$, equals $-1$. Now I know that $F^*$ is cyclic, so taking the product over $1,l,l^2,\ldots,l^{|F^*|}-1$, where $l$ generates $F^*$ really is the product of all…
user16008
  • 255
2
votes
3 answers

Can there be a Finite Field That Does Use Not Modular Arithmetic?

This may be a rather silly question, but I'm puzzled that (at least so far as I can tell) all finite fields use modular arithmetic. Is there no other way to construct a finite field than by defining addition and multiplication in terms of the…
Nobody
  • 999
2
votes
1 answer

Which powers of a primitive element of a finite field yield a generator of a finite field extension?

Let $F_{q^m}$ denote the finite field with $q^m$ elements. Let $\gamma$ be a primitive element of $F_{q^m}$. What are the powers $i$ such that $F_q(\gamma^i)=F_{q^m}$? Note that the following are equivalent, so the question could be rephrased…
geo909
  • 532
2
votes
1 answer

When is $c\alpha$ primitive, for nonzero $c\in GF(q)$ and $\alpha$ primitive in $GF(q^m)$?

Let $q$ prime power and $\alpha \in GF(q^m)$ be primitive element. When is $c\alpha$ still primitive in $GF(q^m)$? EDIT: More generally, if $\alpha \in GF(q^m)$ is any non-zero element, I'm also wondering if we can say something about the order of…
geo909
  • 532
2
votes
1 answer

$x=y^p-y$, $y \in \mathbb{F}_{p^2}$. Prove: $x^2 \in \mathbb{F}_p$

Im practicing for an exam, can anyone help me with this? Let $p$ be prime and let $x=y^p-y$, for $y \in \mathbb{F}_{p^2}$. Prove: $x^2 \in \mathbb{F}_p$
2
votes
1 answer

Canonical representation of finite field

If there a canonical representation of finite fields $\Bbb F_{p^n}$ for $n>1$? By canonical I mean that if I were to say to someone else "this bunch of bits represents an element of $\Bbb F_{p^n}$", he'd be able to find that element without needing…
xavierm02
  • 7,495
2
votes
1 answer

How to construct $\mathbb{GF}(4^2)$ from $\mathbb{GF}(4)$?

I know how to construct $\mathbb{GF}(2^m)$ from $\mathbb{GF}(2)$: First we find a primitive polynomial of degree $m$ over $\mathbb{GF}(2)$ then assuming $\alpha$ as one of it's roots, consecutive powers of $\alpha$ will be elements of…
2
votes
0 answers

Number of solutions of $x^m \neq y^m$, $z^n=w^n=t^n$ over a finite field.

I am trying to compute the number of solutions of the following system of equations over a finite field $\mathbb{F}_q$ ($q$ may be considered odd prime power or just odd prime if needed): $$ x^m \neq y^m,\\ z^n = w^n = t^n, $$ where all $x$, $y$,…
2
votes
1 answer

Derivative of polynomial in GF(9)

I'd like to calculate derivative of polynomial in $GF(9)\equiv GF(3^2)$. For polynomials in fields of characteristic of $2$ it is quite easy, because operations are modulo 2 which means that there are multiplications by 1 or 0. But in GF(3)…
scdmb
  • 369
2
votes
3 answers

Multiplicative inverses for elements in field

How to compute multiplicative inverses for elements in any simple (not extended) finite field? I mean an algorithm which can be implemented in software.
scdmb
  • 369