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

Is there a fast way to factor polynomials with finite field $\operatorname{GF}(p^k)$ coefficients?

For example the 33-term polynomial $x^{32} + c_{31} x^{31} + \ldots + c_1 x + c_0$, where the coefficients are 16-bit finite field numbers. For the cases I'm considering, the 33-term polynomial will have 16 quadratic factors of the form $x^2 + a x +…
rcgldr
  • 546
2
votes
1 answer

Why are $q$-polynomials commutative while linear transformations are not?

There is a one-to-one correspondence between those $q$-polynomials over $\mathbb{F}_{q^n}$ of the form$$\sum_{i=0}^{n-1}a_ix^{q^i},$$ and those linear transformations of $\mathbb{F}_{q^n}$ over $\mathbb{F}_q$. However, for two $q$-polynomials…
user735332
2
votes
1 answer

The maximum number of some elements in the finite field.

Consider the finite field $\mathbb{F}_{p^q}$ for some $p$ and $q$ where $p$ is a prime number. Suppose that $r$ in $\mathbb{F}_{p^q}$ has multiplicative order $n$. Consider the set ${\bf L}=\{0,1,r,r^2,\cdots ,r^{n-1}\}$. Let the elements of ${\bf…
user0410
  • 582
2
votes
1 answer

Difference between splitting field of $X^{15}-2$ and $X^{15}-1$ over finite field $\mathbb{F}_7$

Find the splitting field of polynomial $f(X)=X^{15}-2\in \mathbb{F}_ 7[X]$. Splitting field of this polynomial should be of the form $\mathbb{F}_{7^n}$ for some suitable $n$. For example, I know how to solve the much easier problem if we consider…
RFZ
  • 16,814
2
votes
0 answers

Discrete Logarithm Problem in Finite Fields

Consider the finite field $\mathbb{F}_{\displaystyle{3^{23}}}$ which is constructed from the primitive polynomial ${\bf f}=x^{23}-x^3+1$ over $\mathbb{F}_3$. Let $\alpha$ be a root of $\bf f$. Suppose that $\beta$ is a polynomial based on the…
user0410
  • 582
2
votes
2 answers

The meaning of properties of XOR operation in $GF(2^n)$

In Cryptograph, I read some explanation about Exclusive-Or operation in Galois Field. The five properties of the exclusive-or operation in the $GF(2^n)$ field makes this operation a very interesting component for use in a block cipher: closure,…
haram
  • 147
2
votes
1 answer

Algebra, finite fields

As I understood, a minimal polynomial for some $A$ over a finite field is an irreducible polynomial with a minimal degree for which $A$ is a "root". However, I can't understand how to find one. For example, if we have an element of order 13 over…
2
votes
4 answers

$x^3+2x+2 \in \mathbb{F}_3[x]$. Let $\alpha$ be a root in some extension field.

One can see by brute force that $x^3+2x+2$ has no roots in GF(3). So it is irreducible and hence the minimal polynomial of $\alpha$. My question is what is $\alpha$, how can I think about it? I determined that $GF(3)(\alpha) \cong GF(3^3)=GF(27)$. I…
2
votes
0 answers

Finite field with $3$rd primitive root of unity.

I like to find those finite field $GF(p^n)$ which contains primitive $3$rd root of unity. One thing is clear that $GF(p^n)^*$ is cyclic group of size $p^n-1. $ So for $3$rd primitive root we must have $3/(p^n-1).$ i.e. $$p^n-1\equiv 0\mod3$$ so for…
neelkanth
  • 6,048
  • 2
  • 30
  • 71
2
votes
3 answers

how to find $|GL_2(F_p)|$

I need to find $|GL_2(F_p)|$, I am very very uncomfortable in counting, so please help here I proceed, $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ be such an invertible matrix, so we need and sufficient that $ad\neq bc$, so if i chose all non zero…
Myshkin
  • 35,974
  • 27
  • 154
  • 332
2
votes
1 answer

Using characters in finite fields to find number of solutions to polynomials.

I am trying to use the theorem below to show that if $d_i=(m_i,p-1)$ then $\sum_ia_ix_i^{m_i}=b$ and $\sum_ia_ix_i^{d_i}=b$ have the same number of solutions. So far, I have been able to prove that if $d=(m,p-1)$ that the number of solutions to…
Steven-Owen
  • 5,556
2
votes
1 answer

Show the polynomial $(x-\alpha)(x-\alpha^p)\cdots(x-\alpha^{p^{n-1}})$ is in $F_p[x]$ if $\alpha\in F_{p^n}$

I need help proving that the polynomial $f(x)=(x-\alpha)(x-\alpha^p)\cdots(x-\alpha^{p^{n-1}})$ is in $F_p[x]$ if $\alpha\in F_{p^n}$. This assertion is trivial for $\alpha$ already in $F_p$. So we assume it's not. We know this polynomial is degree…
Steven-Owen
  • 5,556
2
votes
1 answer

When does $\operatorname{trace} (a)=\operatorname{trace}(a^{-1})$?

We work on fields with even characteristic and know that $\operatorname{trace}(a)=\operatorname{trace}(a^2)$.but when does trace of one member of field equals to its inverse?
2
votes
2 answers

System of equation over GF(211) (corrected)

I have this system of equation. $a+b+c=171, a+2b+4c = 46, a+3b+9c = 170$. My task is to solve this system over $GF(211)$. Is there any special process? Thanks for advice.
kmaci
  • 165
2
votes
1 answer

Affine subspace of finite field intersecting prime subfield

Consider a finite field $\mathbb F_{p^n}$ and let $V = \{ y -y^p \mid y \in \mathbb F_{p^n} \} \subset \mathbb F_{p^n}$. It is not hard to see that $V$ is an $(n-1)$-dimensional vector space over $\mathbb F_p$. Now let $x \in \mathbb F_{p^n}$ and…