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)$.

Filter by
Sorted by
Tagged with
2
votes
0answers
49 views

How quickly find we find a primitive root of unity in $\mathbb{F}_{p^z}$?

If we are working in a finite field of integers adjoined with $z$ values, we have $\mathbb{F}_{p^z}$, assuming that we constructed the field correctly. How quickly can we find a value, $\omega$, that ...
1
vote
1answer
37 views

Finding irreducible polynomial in finite field

I would like to find an irreducible polynomial of degree $3$ in $\mathbb{F}_4$, where $$\mathbb{F}_4 = \{a+b\alpha| \ a, b\in \mathbb{F}_2, \alpha^2 = \alpha + 1\}.$$ I first tried to find an ...
2
votes
3answers
50 views

Number of elements $a\in\mathbb{F}_{5^4}$ such that $\mathbb{F}_{5^4}=\mathbb{F}_5(a)$

Determine the number of elements $a\in\mathbb{F}_{5^4}$ such that $\mathbb{F}_{5^4}=\mathbb{F}_5(a)$, and find the number of irreducible polynomials of degree $4$ in $\mathbb{F}_5[x]$. My thoughts: ...
2
votes
0answers
57 views

A Curve Over Finite Field

Let $f(x)\in \mathbb{F}_q[x]$ and let $X$ be the curve over $\mathbb{F}_q[x]$ defined by $\psi(x,y)=(f(x)-f(y))/(x-y)$. I want to show that if $(a,b)$ is a simple rational point of $X$ then the ...
3
votes
3answers
43 views

$1^{-1}+2^{-1}+\dots+\Big(\frac{p-1}{2}\Big)^{-1} \equiv -\frac{2^p - 2}{p} \mod p$ for an odd prime $p.$

I've reduced a problem down to proving this identity. Unfortunately, I don't know where to even start. There has to be some way of expanding the RHS or combining terms on the LHS, but I don't see it. ...
-1
votes
1answer
29 views

$Q\subset L$ with $G := \text{Gal}(L/Q)$, Is $L$ contained in the field of constructible numbers? [closed]

$Q \subset L$ is a finite Galois extension with $G := \text{Gal}(L/Q)$ and $G$ is isomorphic to $S_3$, the symmetric group on $3$ elements. Is $L$ contained in the field of constructible numbers?
2
votes
1answer
40 views

Minimal extension field of $\mathbb{F}_2$ such that

Find the minimal extension field of $\mathbb{F}_2$ such that this extension contains an element of order $21$? Attempt: I know that such an extension of $\mathbb{F}_2$ is like $\mathbb{F}_{2^s}$ and $...
6
votes
0answers
82 views

The number of unitary circulant matrices over a finite field $\mathbb{F}_{q^2}$

Suppose $\mathbb{F}=\mathbb{F}_{q^2}$, where $q$ is a prime power. The conjugate of elements in $\mathbb{F}$ is defined by $\overline{x}=x^q$. I need to find the number of $n\times n$ unitary ...
0
votes
0answers
40 views

Find splitting field of $(x^3-x^2-x)(x^4-x^2+1)$ over $\mathbb{F}_3$

As written in the title, I have to compute the splitting field of $$(x^3-x^2-x)(x^4-x^2+1)$$ over $\mathbb{F}_3$ I'd like to understand if my attempt is correst, or if I'm missing something. Here's ...
0
votes
1answer
43 views

Find irreducible factors without factorizing [closed]

I have an exercise from my course notes that states: Find how many irreducible factors has $f(x) = x^{26}-1$ over $\mathbb{F}_3$ and their degrees. (don't factorize it) I see immediately that the $...
2
votes
1answer
28 views

Number of Elliptic Curves over Fp

I am a beginner/amateur in the topic according to https://www.math.brown.edu/~jhs/Presentations/WyomingEllipticCurve.pdf on page 45, There are approximately 2p different elliptic curves defined over ...
1
vote
0answers
30 views

Given eigenvectors, what is the set of eigenvalues that makes the matrix have specific coefficients?

I have a $\mathbb{F}_2^{n\times n}$ matrix $P$ = $ \begin{bmatrix} 0 & 0 & \ldots & 0 & -c_0 \\ 1 & 0 & \ldots & 0 & -c_1 \\ 0 & 1 & \ldots & 0 & -c_2 \\...
1
vote
1answer
26 views

Is there an isomorphism of fields between $\mathbb{F}_{3^{2}}$ and $\mathbb{F}=\{a+bi; a,b \in \mathbb{F}_{3}\}$?

if $\mathbb{F}=\{a+bi; a,b \in \mathbb{F}_{3}\}$ where $i=\sqrt{2}=\sqrt{-1}$ and we define $(a+bi)+(c+di):=(a+c)+(b+d)i$ and $(a+bi)\ast (c+di):=(ac-bd)+(ad+bc)i$ Is there an isomorphism of fields ...
1
vote
1answer
63 views

How to find the inverse of elements in a field?

Normally I use the naive method: $$a^{-1} = a \cdot b \bmod p \equiv 1,$$ where b is the inverse of a. Else I love to use Fermat's little theorem: $$a^{p − 1} \equiv 1 \bmod p.$$ By multiplying both ...
0
votes
1answer
11 views

Do diagonal elements in the Galois Field addition tables have to be zeros?

I've seen addition and multiplication tables for Galois Fields, where the addition table is simply modular arithmetic, and some tables where the diagonal elements are zeros (i.e. the additive inverse ...
-1
votes
1answer
37 views

How to construct a field with 25 elements of a given polynomial? [duplicate]

Let us say that the polynomial is $x^2 + 5$ and the field is $\mathbb F_{25}$. Hereby $ax+b$ denotes any element of $\mathbb F_{25}$ with both $a$ and $b$ in the field $\mathbb F_5$.
0
votes
0answers
50 views

How to show that a polynomial is irreducible

How do I show that a polynomial is irreducibel? How do I show that $x^2+1$ is irreducible over the field $F_p$ where $p \equiv 3 \mod 4$? My guess for number 1) is that inserting all numbers $x$ from ...
3
votes
0answers
53 views

How many vectors $w\in V$ such that $v_1,…,v_d,w$ are linearly independent?

Let $K$ be a field with $|K|=q$ elements and let $V$ be a $K$ vector space. If $v_1,...,v_d$ linearly independent in $V$. How many vectors $w\in V$ are there such that $v_1,...,v_d,w$ are linearly ...
0
votes
1answer
21 views

Is there an analog of Sturm sequences for finite fields?

In finite fields, is there anything analogous to Sturm sequences for counting the number of roots of a polynomial in a given interval? Alternatively, showing that there are zero roots in a given ...
0
votes
2answers
45 views

Finite field, basis

In $\mathbb{F}_3^3$, I am given:$$U = \text{span}\left(\begin{pmatrix}0\\1\\2\end{pmatrix}, \begin{pmatrix}1\\1\\1\end{pmatrix}\right),\quad W = \text{span}\left(\begin{pmatrix}-1\\0\\3\end{pmatrix}, \...
-4
votes
1answer
184 views

What is the explanation for why a field cannot have certain values like e.g. 12? [duplicate]

Ok, as far as I understand a field has to look like $\mathbb{F}_{p^n}$. But why? What is the explanation?
0
votes
1answer
35 views

Compute the inertial degrees of two prime ideals e.g the inertial degree of $P/(2)$ where P is prime in $Q[e^{\frac{2\pi i}{23}}]$ lying over (2))

I was reading through Marcus Number Field chapter 3 and I got stuck on exercise 17 Let $K=\mathbb{Q}[\sqrt{-23}]$, $L=\mathbb{Q}[\omega]$ where $\omega=e^{\frac{2\pi i}{23}}$. We know that K $\...
0
votes
1answer
78 views

Demonstrate that $p(x)=q(x)$

I want to demonstrate the following statement. Let $p,q\in \mathbb{GF}_2[x_1,\ldots,x_n]$ be of degree $n$ such that for all $v_1,\ldots,v_n\in\mathbb{GF}_2$, $p(v_1,\ldots,v_n)=q(v_1,\ldots,v_n)$. ...
1
vote
0answers
79 views

Why this polynomial reducible? (composite field)

In galois field of prime 2, in composite field $GF((({2}^2)^2)^2)$, There are irreducible polynomials and reducible polynomials. $GF(2^2):Q_1(x) = x^2+x+1,$ $GF((2^2)^2):Q_2(x) = x^2+x+\phi,$ $\...
-1
votes
2answers
41 views

(Proof verification) there is no homomorphism between a finite field’s additive group to its multiplicative group.

Given a finite field F with additive group $\text{F}^+$ and multiplicative group $\text{F}^{\times}$ Show that there doesn’t exist $f$:$\text{F}^+ \to \text{F}^{\times}$ s.t. $f(x+y)=f(x)f(y)$. Proof ...
0
votes
1answer
30 views

Minimal size of a sumset over $\mathbb{F}_p$

Let $A, B \subseteq \mathbb{F}_p$ ($p$ a prime). How to show that $|A+B| \ge \min\{p, |A|+|B|-1\}$? Since $\mathbb{F}_p$ has only $p$ elements, $\forall S \subseteq \mathbb{F}_p, |S| \ge \min\{p, |S|\}...
1
vote
2answers
88 views

$\mathbb{Z}$ mod $p$ vs. $\mathbb{Z}_p$

What is the difference between working in $\mathbb{Z}$ mod $p$ and working $\mathbb{Z}_p$? I'm mainly interested in the terminology and nomenclature, I understand that the result would be the same. ...
0
votes
1answer
45 views

Calculate order of multiplicative group of finite field

How can one calculate the order of a multiplicative group of a finite field such as: $(\mathbb{F}(2^3) \backslash \{0\}, \times)$ Is it as simple as doing $2^3-1$ ?
0
votes
0answers
18 views

Reed Solomon step by step decodification with an example.

Assuming that we have a RS code with parameters m=5, t=3 defined over the GF(32) with generator poly: ...
3
votes
3answers
78 views

Roots of $x^{p^{n-1}}+\ldots+x^p+x$ in $\mathbb{F}_{p^n}$

Let $\mathbb{F}_q$ denote a field with $q=p^n$ elements, where $p$ is prime. Consider the polynomial $f=x^{p^{n-1}}+\ldots+x^p+x$ and the sets $$ \begin{align*} S&=\{a^p-a:a\in\mathbb{F}_q\},\\ ...
3
votes
1answer
27 views

Absolute value of sum of additive characters of $\mathbb{F}_p$

Consider the absolute value of the following exponential sum: $\left|\sum_{x \in \mathbb{F}_p} \sum_{y \in \mathbb{F}_p}e^{\frac{2\pi i}{p}(ux+vy-wxy)}\right|$ for given $u,v,w\in\mathbb{F}_p$ with ...
1
vote
1answer
113 views

Arithmetic in GF$(2^{32})$ using GF$(2^{16})$ and extensions

Ultimately, I'm looking to implement arithmetic in GF$(2^{32})$. I have a library that implements arithmetic in GF$(2^{16})$ using look-up tables for log and anti-log to implement multiplication, and ...
-1
votes
1answer
39 views

Use of irreducible polynomial in finite field construction

When constructing a finite field $\mathrm{GF}(p^n)$ using polynomials: Why do we need to modulo an irreducible polynomial? What happens if this polynomial is reducible? Does such an irreducible ...
1
vote
0answers
43 views

A field $K$ of order $q=p^r$ contains a subfield $K'$ of order $q'=p^k$ if and only if $k\mid r$.

I was trying to prove the following theorem: A field $K$ of order $q=p^r$ contains a subfield $K'$ of order $q'=p^k$ if and only if $k\mid r$. My attempt at the proof was: $K'\setminus\{0\}$ is ...
1
vote
0answers
17 views

How to find an irreducible polynomial over a finite field with a primitive root (and low hamming weight)

I found there that a polynomial in $F[x]$ with $|F| =q $ with degree $n$ will have its roots in $K$ of order $q^n$ Here, I found that either all the roots are primitive or none of them are. I am ...
1
vote
0answers
27 views

Does desingularization of projective curve over finite field add new points?

Let $C: F(x,y,z)=0$ be the projective curve over $\mathbb{F}_{13}$ given bellow. $C$ has only two rational points, both singular and the genus of $C$ is one. To satisfy the Hasse-Weil bound, the ...
0
votes
1answer
37 views

Factorization of polynomials in Galois Field 2

I want to know what is the general rule for factorization of the generator polynomial which is based on Galois Field, GF2? Fact is, a generator of degree m must divide ...
2
votes
3answers
56 views

Roots of $x^{30}-1$ in a finite polynomial quotent field.

Let $F=\mathbb{Z}/5\mathbb{Z} [x]$ (polynomials with coefficients in $\mathbb{Z}/5\mathbb{Z}$) and $I=(x^2 + \overline{2})$ be the ideal generated by $x^2 + \overline{2}$ . Consider the quotent field $...
0
votes
1answer
90 views

Linearly independent vectors over a field and its subfield

Let $\mathrm{F}_q$ be a subfield of $\mathrm{F}_{q^m}$. $\mathrm{F}_{q^m}$ can be seen as an $m$-dimensional vector space over $\mathrm{F}_q$. Let $v_1,\ldots, v_k \in \mathrm{F}_{q^m}^n$ be linearly ...
0
votes
0answers
32 views

If p (mod 4) = 3 and p is a Gaussian Prime. How to show that Z[i]/(p) is equal to GF(p^2)/(x^2+1)?

I currently work with Gaussian Integer. I try to use prime Gaussian Integer field for Elliptic Curve instead of prime field. . We know that every finite field isomorphic to polynomial field with ...
1
vote
1answer
32 views

Degree of Permutation Polynomials

In my algebra course we just started the topic of Permutation Polynomial, and I am trying to prove that is $f \in F_q[x]$ is a permutation polynomial over $F_{q^n}$, $n \geq 1$, then $f$ is a ...
5
votes
1answer
98 views

Unable to invert matrix on Galois Field, even though the matrix should be invertible by construction

We are trying to implement a general file recovery algorithm using Galois Fields. We have implemented the operations for Galois Fields GF(2^8) succesfully, but we're are running into a problem for the ...
3
votes
0answers
107 views

When are Hamming codes cyclic?

Motivation The following statement appears to be true: The $q$-ary Hamming code of codimension $r$ over $\mathbb{F}_q$ is equivalent to a cyclic code if and only if if $q-1$ and $r$ are coprime. ...
2
votes
2answers
23 views

Minimum weight of ternary Golay code in cyclic form

Motivation One of the various approaches to the perfect Golay codes is via cyclic codes. From the cyclotomic cosets, one computes the corresponding cyclotomic coset (2 possibilities each) and can use ...
0
votes
1answer
52 views

Degree of splitting field is either $1$ or $2$

Let $p$ be a prime with $p\not=2,3$. Prove that the degree of the splitting field of $x^{12}-1$ over $\mathbb{F}_p$ is either $1$ or $2$. Give a rule to determine when the degree is $1$ and when the ...
0
votes
0answers
12 views

One-dimensional representations of a cyclic group over a finite field

I need to describe all the representation of $\mathbb{Z}/ n \mathbb{Z} $ over $\mathbb{F}_q$ of the dimension 1. It is clear that the generator $1 \in \mathbb{Z}/ n \mathbb{Z} $ acts on $\mathbb{F}...
1
vote
2answers
89 views

How are the addition and multiplication tables for $GF(4)$ constructed?

I know this question has been asked many times and there is good information out there which has clarified a lot for me but I still do not understand how the addition and multiplication tables for $GF(...
1
vote
1answer
32 views

showing $x^4+x^2+x+1$ is reducible in $GF(81)=GF(3^4)$

I am trying to show that in $GF(81)=GF(3^4)$, $$x^4+x^2+x+1$$ is reducible I proved that it was irreducible in $\mathbb{Z}_3$ How can I prove this ? More generally, how to prove if a polynomial ...
0
votes
1answer
15 views

Modulus operation for polynomials over GF(2)

If I treat the coefficients as an array of boolean values, I would achieve multiplication by using the AND operator and addition by using XOR. How would I go about finding the remainder? Is there, ...
0
votes
1answer
41 views

Degree of extension over finite fields with two elements having same degree irreducible

I get that Q(√2,√3) has degree 4 over Q. Now consider finite field F and a,b lying in an extension of F having same degree irreducible polynomial over F, let it be 'd'. Is the extension F(a,b), of ...

1 2
3
4 5
83