Finite fields are structures arising in abstract algebra. 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)$.

learn more… | top users | synonyms (1)

1
vote
1answer
19 views

Recurrence Relations for Sequence Counting Hamming Weights

Define $a(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=0, ||x||=k\}|$ and $b(n,k)=|\{x \in \mathbb{F}^{2n}_2 : Hx=1, ||x||=k\}|$ where $||\cdot||$ denotes the Hamming weight of $x$ (i.e. number of non-zero ...
3
votes
4answers
51 views

Establishing additive and multiplicative inverses for a finite field

I am struggling with the following problem: Let $F$ be a finite field, and let $G$ be a subset of $F$ with the following properties: $0$ and $1$ are in $G$; whenever $a$ and $b$ are in $G$, $a + ...
4
votes
1answer
35 views

Distribution of the sumset of two GF($q$) subsets

First, a simple definition. The sumset of two subsets $\mathcal{S}_1$ and $\mathcal{S}_2$ containing $GF(q)$ elements is defined as: $$\mathcal{S}_1 + \mathcal{S}_2 = \left\{ s_1 + s_2:s_1 \in ...
0
votes
0answers
24 views

Question on primitive element for extensions of finite fields [duplicate]

I was given this question in field theory class which I am stumped on as after some effort I still cannot tackle. I am given a general natural number $n>1$ and am asked to prove or disprove: ...
4
votes
1answer
39 views

splitting field of $x^8-1$ over $\mathbb F_3$

Suppose $F=\mathbb F_3$ and $f(x)=x^8-1$ in $F[x]$. I tried finding the Galois group of the splitting field of $f(x)$ over $F$ and I'm not so sure if what I did was correct. I began by looking at ...
1
vote
0answers
57 views

Existential theory

I am reading the following about (positive) existential theory: Could you explain to me the last sentence of the Lemma $1.6$ ? Why does this hold?
4
votes
2answers
53 views

primitive element $a$ of $\mathbb F_{p^n}/\mathbb F_p$ such that $a^n\in\mathbb F_p$

Is it true that for every $n\in \mathbb N$ there exists a prime $p$ such that the extension $\mathbb F_{p^n}/\mathbb F_p$ has a primitive element $a\in \mathbb F_{p^n}$ and $a^n\in\mathbb F_p$? I ...
3
votes
4answers
2k views

Calculate 2000! (mod 2003)

Calculate 2000! (mod 2003) This can easily be solved by programming but is there a way to solve it, possibly with knowledge about finite fields? (2003 is a prime number, so mod(2003) is a finite ...
2
votes
3answers
37 views

Question on a passage from “Rational Points on Elliptic Curves”

I was reading the book "Rational Points on Elliptic Curves", when I've crossed with the following passage: "(...) since $3$ does not divide the order $p-1$ (where $p$ is a prime) of the cyclic group ...
1
vote
2answers
58 views

How do we define how many lines lie on a given hypersurface in $\mathbb{F}_q^n$

Given the following surface, for example: $$\mathbb{H} = \{(z_1,z_2,z_3,z_4,z_5)\in \mathbb{F}_{p^2}: z_1 - z_1^p - z_2z_3^p + z_2^pz_3 - z_4z_5^p + z_4^pz_5 = 0\}$$ in $\mathbb{F}^5_{p^2}$. We know ...
3
votes
1answer
35 views

Question on finite fields and their extensions

I have been given this question in Algebra class on finite fields which I have tried to solve but to no avail, so all help appreciated. I am given $ p=13;q=p^6 $, then I am asked to prove or give a ...
3
votes
1answer
60 views

How many points does the surface $\mathbb{H}$ defined with the stated expression contain in $\mathbb{F}^5_{p^2}$?

How many points does the surface $$\mathbb{H} = \{(z_1,z_2,z_3,z_4,z_5)\in \mathbb{F}_{p^2}: z_1 - z_1^p - z_2z_3^p + z_2^pz_3 - z_4z_5^p + z_4^pz_5 = 0\}$$ contain in $\mathbb{F}^5_{p^2}$? ...
0
votes
2answers
34 views

Show that $G = SL_3(F_p)$ acts transitively on $H = F_p^3\setminus \lbrace0\rbrace$

I need to show that $G = SL_3(F_p)$ acts transitively on $H = F_p^3\setminus \lbrace0\rbrace$. That means to show that, for all $s,t \in H$, there is $g \in G$ such that $gt = s$. I tried to make ...
1
vote
1answer
31 views

How original RS codes and the corresponding BCH codes are related?

In 1960, Reed and Solomon suggest the codeword for a message $[x_0\ x_1\ \ldots\ x_k]$ as follows: $$[P_{(0)}\ P_{(\alpha)}\ P_{(\alpha^2)}\ \cdots\ P_{(\alpha^{2^m-1})}]$$ Where $$P_{(t)}=x_0 ...
2
votes
1answer
61 views

All primes $p$ for which $x^{2} +1$ irreducible over $\mathbb{F}_{p}$

Let $\mathbb{F}_{p}$ be the field with $p$ elements. Determine all primes $p$ for which $x^{2}+1$ is irreducible over $\mathbb{F}_{p}$. Here's what I've got. I think this might be finished but I'm ...
2
votes
0answers
56 views

Finite Ramanujan expansions over a finite field

I'm wondering if we could have an analogy in finite fields. After all, the Discrete Fourier Transform (DFT) has been generalized to finite fields as well (with essentially identical properties as in ...
5
votes
2answers
141 views

Infinite sum of elements in a finite field

This is a bit of a curiosity that intrigues me. Let $p$ be a prime and consider the sum of reciprocals of squares divisible by $p$. This is just $$ \dfrac{1}{p^2}\sum_{n=1}^\infty \dfrac{1}{n^2} = ...
12
votes
0answers
122 views

A “generalized field” with $q$ elements, when $q$ is any number?

It is well-known that if a finite field has $q \in \mathbb{N}$ elements, then $q$ is prime power and $q > 1$. However, various modification of the concept of a "field" have been made in order to ...
1
vote
6answers
109 views

In a field $F=\{0,1,x\}$, how does $1 + 1 = x$?

I understand that in a field with two elements $1 + 1 = 0$, but in a field with three I do not understand how $1 + 1 =x$. The work I have done so far is: \begin{align} 1 + 1 &= \{ 0 , 1 , x\}\\ 1 ...
6
votes
2answers
73 views

Embedding $\mathbb{F}_{q^2}^*$ into $GL_2(\mathbb{F}_{q})$

If we see $\mathbb{F}_{q^2}$ as a $2$-dimensional vector space over $\mathbb{F}_{q}$ (and pick a base) then we can identify $\operatorname{Aut}_{\mathbb{F}_{q}}(\mathbb{F}_{q^2})$ with ...
0
votes
0answers
30 views

Requesting programming implementations for $\mathbb{F}_{p^n}$ and $SL_2(\mathbb{F}_{p^n})$.

I would like a programming language capable of doing computations over finite fields and matrix groups over those finites fields. I do not want to have to construct bases and what not on my own. What ...
2
votes
1answer
29 views

Count the number of monic irreducible polynomials of degree 12 over $\mathbb F_q$

This is a qualifying problem. I cannot understand how the inclusion exclusion principle work here in detail. However, I have an argument which leads to a different answer. I am not sure ...
4
votes
1answer
42 views

Number of Solutions to Polynomials in Finite Fields

Let $\mathbb{F}$ be a finite field and $f_i\in\mathbb{F}[x_1,x_2,\ldots,x_n]$ be polynomials of degree $d_i$, where $1\leq i\leq r$, such that $f_i(0,\ldots,0) = 0$ for all $i$. Show that if ...
2
votes
1answer
53 views

Determining parity of the multiplicative inverse?

Let $\mathbb{F}_p$ be a finite field of characteristic $p > 2$, for a fixed $p$. I will consider only prime fields, not $GF(p^n)$. Represent the $p$ elements of the field as integers $\{0,1,\ldots ...
1
vote
0answers
60 views

Dirichlet characters with values in a finite field

Although the classical Dirichlet characters are complex valued, it seems to me rather useful that the characters attain values in a finite field; thus homomorphisms from $\mathbb{Z}_N^*$ to ...
6
votes
0answers
80 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
1
vote
2answers
43 views

How to find orthogonal vectors in GF(2)

I've 13 rows in a matrix, which are linearly independent.(number of columns is 20), in GF(2). Now i have to find 20 orthogonal vectors in GF(2). I've added 20 more rows which are the rows of an ...
2
votes
1answer
19 views

Unit group of a field is divisible

In the lecture notes on Valuation theory, in Ex. $1.16$ on page $11$ we are asked to show that: If $k$ is an algebraically closed field, then $k^{\times}$ is a divisible abelian group. Isnt $k = ...
9
votes
3answers
175 views

Counting points on the Klein quartic

In Moreno's book "Algebraic Curves over Finite Fields", he mentions the following in passing with no further comments ($K$ denotes the Klein quartic defined by $X^3 Y + Y^3 Z + Z^3 X = 0$): The ...
7
votes
3answers
139 views

How can I prove irreducibility of polynomial over a finite field?

I want to prove what $x^{10} +x^3+1$ is irreducible over a field $\mathbb F_{2}$ and $x^5$ + $x^4 +x^3 + x^2 +x -1$ is reducible over $\mathbb F_{3}$. As far as I know Eisenstein criteria won't ...
1
vote
0answers
19 views

Computing number of irreducible polynomials of degree n over $\mathbb{F}_q$

When I try to find the number of irreducible polynomials (of degree n) over a finite field I first look for the number of $\alpha \in \mathbb{F}_{q^n}$ such that ...
4
votes
3answers
142 views

Four questions about finite fields

Is $\mathbb{F}_5$ a subfield of $\mathbb{F}_7$? I can think of the answer 'yes' because they have the same set op operations $+ \cdot$ and the answer 'no' because in $\mathbb{F}_5: 2\cdot3=1$ and in ...
1
vote
3answers
26 views

Finding an isomorphism between polyomial quotient rings

Let $F_1 = \mathbb{Z}_5[x]/(x^2+x+1)$ and $F_2 = \mathbb{Z}_5[x]/(x^2+3)$. Note neither $x^2+x+1$ nor $x^2+3$ has a root in $\mathbb{Z}_5$, so that each of the above are fields of order 25, and hence ...
2
votes
1answer
52 views

How does the multiplicative group of a finite field, considered as a vector space, act on subspaces?

Given that a finite vector space $V = \operatorname{GF}(p)^n$ corresponds to the finite field $F = \operatorname{GF}(p^n)$, I'm wondering about how the multiplicative subgroup of $F$, $F^*$, acts on ...
0
votes
1answer
27 views

What is the exponent in the definition of a Galois field called?

From what I understand, when speaking of a Galois field $\operatorname{GF}(p^k)$, $p$ is called the characteristic of the field, and $p^k$ is the order. Does $k$ have a name by itself?
4
votes
2answers
139 views

Modular curves over finite fields

I'm looking for a detailed reference for modular curves over finite fields, such as $X(N)$, $X_1(N)$, and $X_0(N)$. There seems to be a lot of literature dealing with them over $\mathbb{C}$, but I'm ...
1
vote
1answer
38 views

List all elements in the residue field $Z[i]/(q)$

Consider a Gaußian prime $q$. How to list all elements in the residue field $Z[i]/(q)$? Is there any formulas or criteria? Here I'm looking for the case $q$ is a complex number, as I can do the real ...
2
votes
2answers
64 views

Proof that algebraically closed fields of characteristic $p$ exist

How do you prove that algebraically closed fields of characteristic $p$ exist? I have also read: For a finite field of prime power order $q$, the algebraic closure is a countably infinite field ...
2
votes
1answer
34 views

Sum of powers in finite fields

I have trouble following the logic in this proof. In particular, why is the following equality is true: $$\displaystyle\sum_{x \in K^\times} x^u = \displaystyle\sum_{x \in K^\times} y^u x^u$$
3
votes
2answers
93 views

Polynomials over a finite field

Let $\mathbb{F}_p$ be a finite field where $p$ is a prime. Consider the following set of polynomials over $\mathbb{F}_p$: $$G_n(p)=\{{x+a_2x^2+\cdots+a_nx^n\mid a_i\in \mathbb{F}_p}\}.$$ Is ...
1
vote
1answer
50 views

How does one construct the Galois field extension $GF((2^2)^3)$?

Looking at past exam question, one asks us to construct a Galois field extension $GF((2^2)^3)$ whenever the primitive irreducible polynomial $p(X) = X^3 + \alpha X^2 + \alpha X + \alpha \in ...
0
votes
1answer
53 views

Is finding generators of finite fields hard?

Task: Given $n$, find a generator of $GF(n)^*$. Is there any evidence this is hard? Maybe a reduction from another problem presumed hard? Finding the orders of elements should be hard because I ...
5
votes
2answers
109 views

Existence of ring homomorphism from $\mathbb{Z}[\frac{i}{2}]$ to a finite field

Does a ring homomorphism from $\mathbb{Z}[\frac{i}{2}]$ to a finite field with characteristic $p\equiv 3 \bmod 4$ such that the unity is mapped onto the unity exist? Thank for your help.
2
votes
1answer
53 views

Some questions on elliptic curves over finite fields

Let $E$ be an elliptic curve defined over $\mathbb{F}_q$. For a prime $\ell \neq q$, we have that the $\ell$-torsion subgroup $E[\ell] \cong (\mathbb{Z}/\ell \mathbb{Z})^2$. As can be easily seen, ...
0
votes
0answers
30 views

Prove that the coefficients of a polynomial are in a finite field

I am trying to understand the proof of the following statement: Let $\mathscr{θ}$ be an algebraic element over the finite field $F$ and $\mathscr{θ=θ_1,θ_2 ... θ_n}$ be all the conjugate elementes of ...
1
vote
2answers
57 views

Why are these curves' points called rational?

While studying curves defined over finite field $\mathbb F_q$, it's said that the points of the curve are the rational points. Why is it said like this? For example, if $q$ is prime, aren't we just ...
2
votes
1answer
40 views

A count involving number of subspaces

Let $V$ be an $n$ dimensional vector space over a finite field with $q$ elements and $W$ be a fixed $k$ dimensional subspaces of $V$. How to find the number of distinct subspaces $X$ of $V$ such that ...
1
vote
3answers
45 views

List the elements of the field $K = \mathbb{Z}_2[x]/f(x)$ where $f(x)=x^5+x^4+1$ and is irreducible

Since $\dim_{\mathbb{Z}_2} K = \deg f(x)=5$, $K$ has $2^5=32$ elements. So constructing the field $K$, I get: \begin{array}{|c|c|c|} \hline \text{polynomial} & \text{power of $x$} & ...
2
votes
1answer
40 views

FSR function of the component-wise product, sum, of two LFSR sequences

Let $T_1$, $T_2$ be two $m$-sequences over $\mathbb{F}_q$ of length $q^n-1$, say $T_1 = (\text{Tr}_{q^n | q}(\alpha^i))_{i \geq 0}$, $T_2 = (\text{Tr}_{q^n | q}(\beta^i))_{i \geq 0}$, for some ...
3
votes
1answer
65 views

Discriminant of Polynomials (Galois Theory)

So I'm reading Dummit and Foote and they define the discriminant of $x_{1},...,x_{n}$ by $$D=\prod_{i<j}(x_{i}-x_{j})^2$$ and the discriminant of a polynomial to be the discriminant of the roots. ...