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
0 answers

What will be the size of this integral domain?

Let $(R,+,*)$ be an integral domain such that $a*a =a$ for all $a\in R$. What will be the size of $|R|$? My attempt : $|R| = 1$, as $a*a=a$ by cancellation law $a = e$ which means $|R|=1$
abaa
  • 101
0
votes
0 answers

What is the general algorithm for factoring a polynomial in $GF(n)$?

What should I start with when I want to factor a polynomial over $GF(n)$? Should I start by finding it's irreducible polynomials? Say, I have $x^4+3x^3+4x+1$ and I want to factor it over $GF(5)$ What should I start with when I see a problem like…
0
votes
1 answer

Prove that every monic polynomial $f$ irreducible in $\mathbb {F}_q[x]$ has $\deg(f)$ roots in a finite extension $ E $ such that …

Prove that every monic polynomial $f$ irreducible in $\mathbb {F}_q[x]$ has $\deg(f)$ roots in a finite extension $ E $ such that $\deg(f) \mid s$ and $[E: \mathbb{F}_q] = s$. The book I'm reading uses this fact without giving a proof; why is this…
0
votes
1 answer

Consider Galois field GF(2^m) .Why does the following quadratic equation tour the entire field?

#include #include #include #include int cmp(const void *a, const void *b) { unsigned long A=*(unsigned long *) a; unsigned long B=*(unsigned long *) b; if( A < B) return (-1); else if (A > B)…
0
votes
1 answer

How many elements does the Field $Z_{5[x]}/f(x)$ have?

In class we are learning about finite fields and polynomials in finite fields my professor wrote that $Z_{5[x]}/f(x)$ where $f(x)=x^3+x+1$ Here P = 5, n = 3 $|F|=5^3=125$ So F has 125 elements I'm a bit confused as to how he determined this,…
Temirzhan
  • 983
  • 1
  • 11
  • 25
0
votes
1 answer

Reducing a polynomial $ℤ\bmod 2$

I have the following polynomial $$g(x)=x^6+x^5+x^4+x^2 \in ℤ \bmod 2$$ I'm having trouble finding information on how to reduce this polynomial, Or let alone being able to tell if it is reducible in the first place. If the polynomial has a root…
Temirzhan
  • 983
  • 1
  • 11
  • 25
0
votes
3 answers

Total number of directions in $F_q^2$ is $q+1$

According to this paper (https://arxiv.org/pdf/0803.3525.pdf), at the beginning of page 3, the total number of directions in $F_q^2$ is $q+1$. Here I believe that direction means the number of distinct lines of the form $L_{y} = \{ty \mid y \in…
Alex
  • 259
0
votes
0 answers

Finding matrix for mapping members of isomorphism finite fields

I have trouble finding a matrix for mapping the members of isomorphism finite fields. For example, for two $GF(2^8)$s constructed from two distinct irreducible polynomials of degree 8, is there any matrix mapping the corresponding members of two…
Khalesi
  • 11
0
votes
3 answers

linear independence in GF(3)

I have a question regarding linear independence in finite fields, more specifically the GF(3)-field. My textbook claims that $ (1,2,0)^T,(2,1,0)^T,(0,0,1)^T, $ are linearly independent wrt. the field $\mathbb{R}$, but not wrt. GF(3). I've googled…
1233023
  • 543
0
votes
0 answers

finite field and relationship between subfield and subgroup

Please help or hints me to solve this question: Prove: if $F$ is a finite field, then $H \cup \{0\}$ is a subfield of $F$ for every subgroup $H$ of the multiplicative group $F^*$ if and only if the order of $F^*$ is either $1$ or a prime number of…
Masoud
  • 425
0
votes
1 answer

Primitive elements of finite field with characteristic 2

How would you find primitive elements of the finite field $\mathbb{F}_{2^c}$ for arbitrary integer $c\geq 1$? Is there some general way of doing this? I in fact only want to find one for each $c$ if there happens to be one that is simple to…
user66307
0
votes
1 answer

Minimum distance in linear code

Imagine I have $C (n,k,d)$ - linear code above $GF(q)$. Consider I know all words of this code. $c_1, ..., c_M$ -- vectors from it. If matrix H -- checking matrix (so any word from code will give zero in this way: $vH=0$ for this code will be $H =…
user324463
0
votes
1 answer

Why does $x^2+y=0$ have 8 zeroes?

Does anyone know why $x^2+y=0$ has 8 zeroes in $(\mathbb{F_9^*})^2$? Maybe I can show this with the primitive element but I'm not sure if this really works like that.
0
votes
0 answers

Find the values of the expression in $ GF(16) $ , the finite field

Find the values of \begin{align} (a) \ x^{12}*x^{10} \ as \ a \ sum \ of \ power \ of \ x \\ (b) (x^{2}+1)*(x^{3}+1) \ as \ single \ power \ of \ x \end{align} in $ GF(16) $ from the following table: $$ $$ I have tried as- (a) $…
MAS
  • 10,638
0
votes
1 answer

Normal basis of $GF(2^m)$ over $GF(2)$

Can someone help me to understand how to find normal basis of $GF(2^m)$ over $GF(2)$. For example $GF(2^{60})$. I need to multiply polynomials in this field and I would like to use the normal basis to do it but I don't understand how to find the…
aicha
  • 1