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
1
vote
3 answers

The elements in a finite field.

I am reading some lecture notes from MIT Open Courseware. One of the theorems states that the elements in a finite field of order $q$ are the $q$ distinct roots of the polynomial $x^q - x$. I can see that the nonzero roots of this polynomial would…
1
vote
0 answers

Galois subfields

S R Wicker in his book states ... $GF(p^m)$ has all sub-fields of order $p^b$ provided $b$ divides $m$. Qn: In order to have a sub-filed of order $p^b$ shouldn't we have also the constraint: $p^b - 1$ divides $p^m -1$ ? (that is to say, the…
1
vote
0 answers

How to evaluate this function in F_p efficiently?

For the positive prime integer $p$, Let $\mathbb{F}_p=\{0,1,\cdots, p-1\}$ be the finite field of order $p$. For $x\in \mathbb{F}_p$, define $f_p(x)$ to be the maximum element in the set $\{ x^n+x^{-n}\in \mathbb{F}_p | n\in {\mathbb{Z}}\}$. For…
Module
  • 81
1
vote
2 answers

root of irreducible polynomial

I have just started studying finite fields and I'm confused by the language around irreducible polynomial and find the following definition confusing: "If $f$ is irreducible in $\mathbb{F}_{q}[x]$ of degree $m$ then $f$ has a root a in…
paule
  • 11
1
vote
0 answers

I need help with constructing the field GF$(2^8)$.

I have to use the polynomial $X^8 + X^4 + X^3 + X^2 +1$, and given $\alpha$ is a primitive element. So far I have that $\alpha^8=\alpha^4 + \alpha^3+\alpha^2+1$, and the only method for finding the elements of the field known to me is to multiply…
Cacey
  • 11
1
vote
0 answers

Is collinearity sufficient for a map to be affine on a cartesian product of finite fields?

Let $V=\mathbb{Z}_p\times \mathbb{Z}_p$, where $p$ is prime. Let $\pi:V\rightarrow V$ be a map such that if two lines are parallel in $V$, then their images remain parallel. This is a property of affine transformations on $V$, so my question is…
JQX
  • 159
1
vote
1 answer

Rijndael S-Box algorithm: Can someone please explain how this code calculates the multiplicative inverse?

Wikipedia's explanation of the Rijndael Cipher's S-Box gives c code for calculating the S-Box. I've been able to calculate the S-Box values using exponent and log look-up tables to calculate the multiplicative inverse, but I can't see how this code…
dohzer
  • 13
1
vote
1 answer

Prove that $F[x]/(f(x))$ has $q^n$ elements

let $F$ be a finite field of order $q$ and let $f(x)$ be a polynomial in $F[x]$ of degree $n \geq 1$. Prove that $F[x]/(f(x))$ has $q^n$ elements. I know that if a field is finite then the order is prime so that means q is prime, but what does that…
user146269
  • 1,855
1
vote
1 answer

Factorization of $x^5-1$ over $F_{11}$ and $F_{19}$

I got the following question. The polynom $x^5-1$ should be factorized over $F_{11}$. I have this as a first solution: $x^5-1=(x-1)(x+1)(x^2+1)(x-1)$ could this be possible? I don't know which irred. polynomials I can use for factorization. Can I…
1
vote
2 answers

Distribution of Trace values

I try to prove that ${2^{n-1}}$ elements of the field $\mathbf{F}_{2^{n}}$ have a Trace with value 1, while the other ${2^{n-1}}$ elements have a Trace with value 0. I started to show that Trace(1) = 1, and I tried to use the additivity of the…
1
vote
0 answers

determining the multiple solutions for GF(2) discrete logarithms of polynomials with partially known coefficients

I have an LFSR, essentially $x^k \mod p(x)$ for some characteristic polynomial with coefficients in GF(2), as outlined in Clark and Weng's article: it has a period (= order of the associated finite field) that is a "smooth" integer (factors are…
Jason S
  • 3,109
1
vote
2 answers

Factoring polynomial in prime field

How is a polynomial like $x^5-1$ be factorised in a prime field like $\mathbb{F}_{11}$ for example ? Any advice ? I was successful in trying all members of $\mathbb{F}_{11}$ to find the roots as described in the answers. Thanks. But I wasn't…
1
vote
1 answer

Subfield of a Field

I read that any field $F$ has a unique smallest subfield $F_0$ (Dummit and Foote : Exercise 7.5.3). Consider the field $F = F_p \times F_p$. $(F_p,0)$ is a sub-field of $F$ since it has a unit $(1,0)$ and every element has an inverse. Obviously…
0
votes
0 answers

find an example for an equation in finite field

Consider the extension field $F_{q^n}$ as a vector space over $F_q$, find two linearly independent elements $\alpha_1$ and $\alpha_2$ in $F_{q^n}$, such that $\alpha_{i}\neq1$, for $i=1,2$, and :…
0
votes
2 answers

Subtraction in GF(2^8) Giving Incorrect Results

Let me preface this by stating that I'm not normally a math person, but I'm currently dabbling in finite fields to help wrap my head around certain cryptographic topics (specifically those based around AES). To my understanding, addition and…
Mr. Llama
  • 103