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)

0
votes
0answers
12 views

Functions that are “balanced” on the support of a permutation

Let $F = GF(2^n)$. Let $P(x), Q(x) \in F[x]$ be such that $P(x)$ is a permutation, while $Q(x)$ is not a permutation. For $\lambda \in F^*$ define the function $g_\lambda(x) = Tr(\lambda Q(x))$. Let ...
0
votes
2answers
30 views

Power in finite field

Does the following statement hold true for any finite field? $$a^p\equiv a \qquad(\mathbb{Z_p})$$ I have tought at it this way: all numbers in $\mathbb{Z_p}$ are $\in \{0,\mathbb{Z_p}\}$ and ...
1
vote
1answer
13 views

Incident vector for lines in a 2D-Euclidean Geometry over Finite field

Consider the 2-D $EG(2,2^2)$ geometry. Let $\alpha$ be a primitive element of $GF(2^{2\times 2})$. The incident vector for the line $\mathcal{L} = \{\alpha^7, \alpha^8, \alpha^{10}, \alpha^{14}\}$ is ...
1
vote
0answers
33 views

$x^p -x-1$ irreducible over $\mathbb{F}_{p}$ [duplicate]

Show that $x^p - x -1$ is irreducible over $\mathbb{F}_{p}$. I've seen this polynomial (or some variation x^p -x -a) on several of our qualifying exams and in every case they ask you to show it is ...
1
vote
0answers
30 views

A finite field subset sum count

Given $d\in\Bbb N$, pick $N=2^{2d}$ distinct $a_j$ from $\big\{1,\dots,2^{d^2}-1\big\}$ and pick $i$ from $\big\{3,\dots,2^{d}\big\}$. On average how many of $i$-subsets in ...
3
votes
1answer
35 views

Cramer Rule Over Finite Field

Let $A=\pmatrix{4&2\\ 0&1},\ b=\pmatrix{5\\ 3}$ and $A\pmatrix{x_1\\ x_2}=b$ over the field $\mathbb Z_7$. What is $x_1$? So we need to calculate $$x_1=\frac{\det(A_1)}{\det(A)}$$ ...
1
vote
1answer
13 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
50 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
32 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
33 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
52 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
51 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
34 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 ...
2
votes
1answer
33 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
28 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
60 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
52 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
137 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} = ...
10
votes
0answers
113 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
93 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
71 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
28 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
41 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
48 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
55 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
73 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
38 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
169 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
137 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
140 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
43 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
131 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
57 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
28 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
90 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
48 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
52 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
106 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
50 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, ...