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
2
votes
1 answer

A count involving number of subspaces

Let $V$ be an $n$ dimensional vector space over a finite field with $q$ elements and $W$ be a fixed $k$ dimensional subspaces of $V$. How to find the number of distinct subspaces $X$ of $V$ such that $W+X=V$? (Here + may or may not be the direct…
2
votes
4 answers

Is every finite field a quotient ring of ${Z}[x]$?

Is every finite field a quotient ring of ${Z}[x]$? For example, how a field with 27 elements can be written as a quotient ring of ${Z}[x]$?
cps
  • 21
2
votes
2 answers

How many quadratic non-residues are there in the image of $f(a) = a^2 - x^2$?

When reading about Cipolla's algorithm on Wikipedia, I found that the number of quadratic non-residues in the image of $f:\Bbb F \longrightarrow \Bbb F, f(a) = a^2 - x^2$ where $\Bbb F$ is a finite field of prime cardinality $p$ and $x \in \Bbb F$,…
wlad
  • 8,185
2
votes
1 answer

Elements of a finite field

What is the proof that for any given element $c$ of $F_q$, there exist two elements $a$ and $b$ of $F_q$ such that $a^2 + b^2 = c$. i know that $q$ is the characteristic of this field, but i don't see how this leads, in any way, to a solution to the…
guthik
  • 429
2
votes
1 answer

Finite field, how to satisfy equation?

Suppose we have $\mathbb{F}_{2^5}$ defined by polynomial $x^5+x^2+1$, and (this is homework exercise, which I kinda solved) it is required to find suitable elements $b$, so that it satisfies equation $b^2+b=x^3+1$ In this field, only 32 items and it…
2
votes
1 answer

Can we rewrite $Tr(ab^2)$ as $Tr(f(a)b)$?

Can we rewrite $Tr(ab^2)$ as $Tr(f(a)b)$ where $Tr:F_{2^{kn}}\rightarrow F_{2^{k}} $ is trace map, $k \neq 1$, $f$ is a function just depends to $a$.
vudu vucu
  • 1,040
2
votes
0 answers

Conversion from/to power form and polynomial basis is a finite field

I'm trying to figure out if there is a way better than $O(m^2)$ of converting between the power form $(\alpha^n)$ to polynomial basis. Right now, I'm just enumerating the entire field up to the $n$-th entry for power form to polynomial basis. To…
2
votes
1 answer

Determining subgroups of a finite field and their elements

I'm studying cryptography and while reading some lecture notes I found the following: $F$*37 has subgroups of order 2 ({20 , 218}), 3 ({20 , 212 , 224}), 4, 6, 9, 12, and 18. How to determine that the subgroups are of order 2, 3, 4, 6, 9, 12, and…
OneZ
  • 31
2
votes
0 answers

How can I predict what numbers "work" without brute force?

I've been doing some research with LFSRs and I have found something I can't explain. I've worked on it for years but I'm finally opening up to public involvement because I can't stand not knowing. Let's say you have an 8 bit LFSR. As a reminder,…
2
votes
1 answer

Frobenius automorphism

Suppose $ q = p^r$. Let $F$ be the splitting field of $X^q - X$. Let $\phi : F \to F$ be the Frobenius automorphism $\phi(x) = x^p$. Then let $F' \subseteq F$ be the fixed field of $ < \phi^r >$. Claim: $x \in F'$ iff $\phi^r(x) = x $. Why is the…
Matt
  • 2,343
1
vote
5 answers

Square root for Galois fields $GF(2^m)$

Can we define a function similar to square root for $G = GF(2^m)$ (Galois field with $2^m$ elements) as $\sqrt{x} = y$ if $y^2 = y \cdot y = x$ ? For which elements $x \in G : \exists y \in G : y^2 = x$ this function would be defined? Can I approach…
IgorK
  • 113
1
vote
1 answer

Associative properties with two numbers

I am working through a number theory text and I am given a set $S=\{A,B\}$ and it has the properties: 1) $A+A=A$ 2) $B+B=A$ 3) $A+B=B+A=B$ 4) $A(A)=A$ 5) $A(B)=B(A)= A$ 6) $B(B)=B$ I am to verify this set conforms to the axioms of a field but the…
1
vote
0 answers

irreducible quadratic trinomial over finite field

In p130 of 《finite field 》 by Lidl et al. : For a trinomial x^2 +x +a over a finite field F_q of odd characteristic it is easily seen it is irreducible over F_q if and only if a is not of the form a = 4^{-1} - b^2, b \in F_q. How can I deduce it and…
1
vote
0 answers

Solve equations over field of size 2

I am trying to solve this problem: Let $\alpha_1x_1 + \alpha_2 x_2 + \alpha_3x_3 + \alpha_4x_4 + \alpha_5 = 0$ and $x_1x_2+x_3x_4=0$ be equations over field of size $2$. Show that we can't choose $\alpha_1,\ldots,\alpha_5$ so that the first…
Ashot
  • 4,753
  • 3
  • 34
  • 61
1
vote
2 answers

Generators of the multiplicative group of GF(2)

GF(3) can be constructed as follows by polynomial $p(x)=x+1$: $0=0$ $1=1$ $\alpha=2$ GF(5) can be constructed as follows by polynomial…
scdmb
  • 369