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

Hamming bound definition and check bit

A e-error-correcting-code, with size of message k bits to encode for each block. How many check bits should I append so that it satisfies hamming bound? Given this definition, $ \frac{k}{n} \leq 1- \frac {\log_{q}Vol_q}{n}$ where $Vol_q (e, n) = 1 +…
waffle
  • 3
0
votes
0 answers

Why is every finite field is a finite extention of a prime field isomorphic to $\mathbb{Z}_p$?

I am studying about finite field and I found my textbook says that "Every finite field is a finite extention of a prime field isomorphic to $\mathbb{Z}_p$". I cannot find a direct proof of this statement. I think it is because 'every field contains…
이승우
  • 153
0
votes
0 answers

Is isomorphic mapping always possible using a matrix multiply?

For example, isomorphic mapping from one $GF(256)$ to a different $GF(256)$, where $map(a)+map(b) = map(a+b)$ and $map(a) \ map(b) = map(a \ b)$ I've always assumed that such mapping can always be implemented doing a multiply using an 8 row by 8…
rcgldr
  • 546
0
votes
0 answers

How to compute the Galois Field (multiply, GF(2^n))?

I'm a rookie for finite fields. I know that the solution of computing multiplication in GF(2^n), needs to use the degree n irreducible polynomial over GF(2). But I have no idea of the details. Here is an example, example $(x-1)^{-1} g(x)$ in…
0
votes
0 answers

Irreductible polynomial on a finite field of degree as large as wanted

Let $\mathbb{F}$ be a finite field, is it true that for any $n\ge 0$ there exists an irreductible polynomial $ P \in \mathbb{F}[X]$ of degree larger than $n$ ?
0
votes
0 answers

Why does $p$ have to be prime on a finite field $\{0,1,...,p-1\}$?

Why does $p$ have to be prime on a finite field $\{0,1,...,p-1\}$? I'm looking at content on elliptic curve cryptography, and the guy brings up finite fields from $0$ to $p-1$ where $p$ is prime. Why is $p$ prime? What's the reasoning behind this?
0
votes
0 answers

valuation of a composition in finite field

Let $P\in\mathbb F_q[X]$ be an irreducible polynomial, $Q\in\mathbb F_q[X]$. Do we have $v_P(Q(X^q))\ge v_P(Q)$ where $v_P$ denotes the $P$-valuation? Obviously, if a root $x_0$ of $P$ is a root of $Q$, then $x_0$ is a root of $Q(X^q)$ too, but I do…
joaopa
  • 1,139
0
votes
1 answer

How many subspaces of $\Bbb{F}_2^n$ have codimension 1

Let $\Bbb{F}_2^n$ be $n$-dimensional vector space over $\Bbb{F}_2$, the two element field. Approximately how many distinct subspaces $U\le \Bbb{F}_2^n$ of codimension 1 (i.e., dimension $n-1$) are there for large $n$? More generally, for fixed $k$,…
Zach Hunter
  • 1,828
0
votes
0 answers

Are there any non-linear invertible functions $GF(q)^n \to GF(q)^n$

I wondered about the classes of invertible functions over $n$-dimensional Galois fields, $f: GF(q)^n \to GF(q)^n$ s.t. $f^{-1}$ exists. I know that all linear mappings, e.g. of the form $f(x) = Gx$ with some matrix $G\in GF(q)^{n\times n}$, are…
Uroc327
  • 133
0
votes
1 answer

On the $\mathbb{F}_p$-automorphisms of a finite field $\mathbb{F}_q$

Let $\mathbb{F}_q$ be a finite field with $q=p^f$ elements. I know that for each $0\leqslant i\leqslant f-1$, the maps $\sigma_i(x)=x^{p^i}$ are $\mathbb{F}_p$-automorphsim of $\mathbb{F}_q$ (so $\sigma_i(x)=x$ for every $x\in \mathbb{F}_p$). Are…
boaz
  • 4,783
0
votes
1 answer

How do you read $\mathbb{F}_2^n$ aloud?

Probably a silly question, but I could not find any reference. How do you read $\mathbb{F}_2^n$ aloud? This appeared when I tried to explain something to non-mathematics people (from other disciplines of science/engineering). $n$-th order…
hola
  • 1,339
0
votes
0 answers

Fourier analytic preliminaries in finite fields and Fourier inversion

Suppose $\mathbb F_q$ is the finite field of order $q$ and $\mathbb{F}_q^d$ is $d$-dimensional vector space over finite field $\mathbb{F}_q$. Given $f:\mathbb{F}_q^d\to \mathbb{C}$, define the Fourier transform $\hat{f}:\mathbb{F}_q^d\to \mathbb{C}$…
RFZ
  • 16,814
0
votes
0 answers

Proof of Unicity of F4 field operations

How does one prove that : $$\exists !(+,\cdot)|(\mathbb{N}_4,+,\cdot)$$ ,with 0,1 neutral elements of +,., is a field, without using brute force ?
0
votes
1 answer

$[\mathbb F_p (t): \mathbb F_p(t^p)] = p?$

Let $p$ be a prime. Try to show that $[\mathbb F_p (t): \mathbb F_p(t^p)] = p$. I tried to search for relevant hints and come across with these posts. Example for non separable elements? Non-separable, infinite field extensions of non-zero…
Benjamin
  • 581
  • 3
  • 13
0
votes
0 answers

Show if the following polynomials are reducible or not

I am asked to show if $f(x)=x^3+x+1$ over $\mathbb{F}_5$ $g(x)=x^4+x+1$ over $\mathbb{F}_2$ are reducible or not. I was able to show in each case they are irreducible. For $f(x)$ I assumed it is reducible and I considered $a$ to be a root. This…
Josh
  • 1,086
  • 4
  • 15