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)$.
4,414
questions
0
votes
0answers
15 views
Complexity of a permutation over finite field $\mathbb{F}_{2^n}$ with a specific cycle structure? [closed]
a little motivation for my questions:
I have very naive and limited knowledge of mathematics and I'm trying to understand computation.
we can represent a computer by a function $f: \mathbb{F}_{2^n}\...
-1
votes
0answers
32 views
Irreducible polynomial in $\mathbb{Z}_{17}$ [duplicate]
Is the polynomial $x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1$ irreducible in $\mathbb{Z}_{17}$? I don't know how to solve it.
Thank you for any help!
2
votes
0answers
20 views
Clubs whose intersections are multiples of six (Oddtown variant)
This is a question about generalizing the famous "Clubs in Oddtown" problem. The original setup is that a town has $n$ people, and $m$ clubs each consisting of a subset of the population. ...
1
vote
1answer
45 views
The smallest extension field of $\mathbb{F}_3$ containing all the zeros of $f(x)=x^{11}-1$
Firstly notice that $f(1)=0$ so $f(x)=(x+2)g(x)$ over $\mathbb{F}_3$ for some $g$. Moreover, $\text{ord}_{11}3 = 5$, ie $5$ is the smallest exponent $t$ such that $3^t=1 \mod 11$, so $5$ is the lcm of ...
8
votes
6answers
210 views
Giving a 1-hour talk to highschool math club: any topic suggestion?
I've been invited (by my kid) to give a one hour talk to her highschool math club. Last year (right before the pandemic hit) I did two such talks on probability, and they loved it. I'm looking for ...
2
votes
1answer
52 views
Primitive element of $\mathbb{F}_{16}^{\times}$
I have to find a primitive element of $\mathbb{F}_{16}^{\times}$. I defined $\mathbb{F}_{16} = \frac{\mathbb{F}_{2}[a]}{\langle a^4+a+1 \rangle}$.
I tried to prove that $a^3$ and $a^5 \neq 1$.
I got $...
-1
votes
1answer
40 views
On the finite algebra $\Bbb F_q[X]_{<n}$ over $\Bbb F_q$
Let us take the vector space of all the polynomials of degree less than $n$ over the finite field $\Bbb F_q$,
\begin{eqnarray*}
\Bbb F_q[X]_{<n} &:=& \{ f(X)\in \Bbb F_q[X]:\deg f(X) <n\}...
1
vote
0answers
22 views
The best methods for multivariate polynomial equations over finite fields
I am trying to get a rough overview of the best methods one might use to find solutions of multivariate polynomial equations over large finite fields. We can suppose for simplicity that the given ...
0
votes
0answers
23 views
Defining set of a cyclic code
I am asked to find a defining set of a binary cyclic code of length 15 which isn't a BCH code.
I already found the 2-cyclotomic cosets:
$C_0 = \{0\}$, $C_1 = \{1,2,4,8\}$, $C_3 = \{3,6,9,12\}$, $C_5 = ...
-1
votes
1answer
20 views
LCM in $\mathbb F_q[T]$
Let $q$ be a power of a prime $p$. We work in $\mathbb F_q[T]$. Put $L_n=\prod_{j=1}^n(T^{q^i}-T)$. Does one have
$$\deg(\mathrm{LCM}(L_{n+1};L^q_n))=\frac{q^{n+2}}{q-1}+o(q^n)$$
when $n\to\infty$?
0
votes
0answers
23 views
Show if the following polynomials are reducible or not
I am asked to show if
$f(x)=x^3+x+1$ over $\mathbb{F}_5$
$g(x)=x^4+x+1$ over $\mathbb{F}_2$
are reducible or not.
I was able to show in each case they are irreducible. For $f(x)$ I assumed it is ...
5
votes
0answers
120 views
Number of points on the elliptic curve $y^2 = x^3 - x$ over $\mathbb{F}_q$
I need to know the value of $\sum_{x \in \mathbb{F}_q} \chi(x^3 - x)$, where $q = p^r$ with $p$ prime and $\chi$ is the Jacobi symbol.
If we take $-x$, we have $\chi((-x)^3 - (-x)) = \chi(-1)\chi(x^3 -...
1
vote
1answer
24 views
How many $(a, b) \in \mathbb{Z}_p^2$ are there such that $ax + b = y \mod p$ for some $x, y \in \mathbb{Z}_p$?
Background: I am trying to convince myself that the family of hash functions $H = \{h_{(a, b)} : \mathbb{Z}_p \rightarrow \mathbb{Z_p}, (a, b) \in \mathbb{Z}_p^2\}$, where $h_{(a, b)}(x) = ax + b \mod{...
0
votes
1answer
39 views
Number of points of the elliptic curve $y^2 + y = x^3$ over $F_q$
Given the elliptic curve $y^2 + y = x^3$ over $\mathbb{F}_q$ ($q=p^r$, where $p$ is prime), I want to prove that if $q \equiv 2 \bmod 3$, then the elliptic curve has $q + 1$ points.
My exercise says ...
4
votes
1answer
54 views
Adjoining element in a finite field $\mathbb F_{p^n}$ to $\mathbb F_p$ to get $\mathbb F_{p^6}$
Given that $p$ is a prime and $n$ is a natural number, I want to know how many $\alpha$ are in $\mathbb F_{p^n}$ such that $\mathbb F_p (\alpha) = \mathbb F_{p^6}$.
I know that $[\mathbb F_{p^6} : \...
2
votes
1answer
32 views
Lower bound for number of points of elliptic curve over finite field
I'm asked this kind of question:
Show there exists $q+1$ points on the elliptic curve over $\mathbb{F}_q$ given by $y^2 = x^3-x$ when $q \equiv 3 (mod 4)$
The fact that I'm asked for an ...
4
votes
1answer
33 views
How to extend scalars of a MeatAxe $kG$-module $M$ given in GAP?
Let $G$ be a finite group. Suppose $k:=\mathbb{F}_5$, let char$(k)\mid |G|$, and let $M$ be a $kG$-module given in GAP, as in the following example:
...
0
votes
1answer
62 views
Extension Galois field, multiplication of elements
Consider the extension field $GF(2^4)$ and the primitive polynomial $P(x)=x^4+x^3+1$. How would I find the result of multiplication of elements $1011$ and $1100$?
My work:
$1011$ corresponds to $\{1x^...
0
votes
1answer
40 views
Prove, that the multiplicative group of a finite field is cyclic. [duplicate]
I have almost completed the proof, I have shown, that there exists an element of order e, where e is min{n:$g^n=1$} and $g\in G$ where $G$ is the multiplicative group of a finite field. Now I noticed, ...
0
votes
1answer
34 views
Express a irreducible polynomial $f(X)$ in the field of characteristic $p>0$ $F[X]$ as $g(X^{p^m})$
$F[X]$ is of the form $a_0+a_1X+...+a_nX^n$ where $a_0,a_1,...a_n\in F\text{ with characteristic p>0}.$
Express $f\in F[X]\ as\ g(X^{p^m})$, where the nonnegative integer m is a large as possible ...
4
votes
0answers
37 views
Period of a linear recurrence mod p
$\newcommand{\FF}{\mathbb{F}} $
$\newcommand{\bs}{\mathbf{s}}$
Given linear recurrence
$$
x_n = a_{1}x_{n-1} + a_{2}x_{n-2} + \cdots + a_kx_{n-k}\pmod p,
$$
for $x_0, x_1, \ldots$ we define its state ...
-1
votes
1answer
34 views
Confusion on the order of $GL_2(\mathbb{F}_p)$
In this question, they show that the order of $GL_2(\mathbb{F}_p)$ is $(p^2-1)(p^2-p)$.
For the first column, there are $p^2$ options, and we need to exclude the $0$ column, so there are $p^2-1$. That'...
0
votes
0answers
29 views
Polynomials divide each other in a finite field implies they are constant multiples of each other
If two polynomials divide each other in a field such as $\mathbb{R}$ or $\mathbb{Q}$, then they certainly have to differ by a constant: $g(x) = k f(x)$.
But what about a finite field? If polynomials ...
1
vote
0answers
21 views
Existence of an indicator function in finite field notation
The indicator function on a set $A$ is a function $1_A:A\to \{0,1\}$ defined by $$1_A(x)= \begin{cases}
1 &\text{if } x\in A \text{ and}\\
0 &\text{if } x\notin A. \end{cases}$$
More ...
6
votes
0answers
144 views
Constructing a “microscopic” error correcting code
I'm a doctor studying tiny specimen under a microscope. I had this strange idea to "barcode" each specimen with a physical barcode. This barcode is assembled from two pigments which can be ...
-1
votes
0answers
45 views
$[\mathbb{F}_{p^n}: \mathbb{F}_p] = n$?
I have seen multiple answers using this fact: $[\mathbb{F}_{p^n}: \mathbb{F}_p] = n$.
Proving that $f(x)$ divides $x^{p^n} - x$ iff $\deg f(x)$ divides $n$
Prove that if $\mathbb{F}_{p^n} \subseteq \...
1
vote
1answer
42 views
Determinant of $\mathbb{F}_2$ square matrices
Let $A_1,A_2,A_3$ and $B$ be in $\mathbb F_2^{n\times n}$. Is $$\mathsf{Det}(A_{1}A_2A_{3}+B)=\mathsf{Det}(A_{1}A_3A_{2}+B)=\mathsf{Det}(A_{3}A_2A_{1}+B)=\mathsf{Det}(A_{2}A_3A_{1}+B)=\mathsf{Det}(A_{...
1
vote
1answer
32 views
Number of squares of the form $a^2+x^2$ in a finite field
Suppose $a$ is a non-zero element in a finite field $GF(q)$ of odd characteristic.
How many $x \in GF(q)$ are such that $a^2+x^2$ is a square in $GF(q)$?
From some experiments with some small fields, ...
2
votes
0answers
42 views
Let $F$ be a field with $|F|=q$ and $[K:F]=2$. Let $αāF$ of order $q-1$. Then there exist an element $β \in K$ of order $q^2-1$ such that $β^{q+1}=α$
Let $F$ be a field with $|F|=q$ and $[K:F]=2$. Let $αāF$ of order $q-1$. Then there exist an element $β \in K$ of order $q^2-1$ such that $β^{q+1}=α$
Am stuck with finding such a $\beta$ of order $q^...
1
vote
1answer
64 views
isomorphism between $\frac{\mathbb{F}_5[x]}{(x^2+x+1)} $ and $ \frac{\mathbb{F}_5[x]}{(x^2 -2)} $
I know $\frac{\mathbb{F}_5[x]}{(x^2+x+1)} $ and $ \frac{\mathbb{F}_5[x]}{(x^2 -2)} $ is isomorphic because they are both 2-degree extension of $ \mathbb{F}_5 $ .
But I cannot contract explicit ...
1
vote
0answers
31 views
Cayley table for the additive and mutiplicative operations in ($\Bbb F_7$, +, *)
I am to construct the Cayley tables for the additive and multiplicative operation in $(\Bbb F_7, +, *)$. I have started by stating
The order (nr of elements) of a finite field must be a prime or ...
5
votes
0answers
58 views
Linear-algebraic interpretation of $q$-multichoose
The $q$-analog $[n]$ of a whole number $n$ is $q^{n-1}+\cdots+q+1$, in which case the binomial and $q$-binomial are
$$ \binom{n}{k}=\frac{n(n-1)\cdots}{k(k-1)\cdots} \qquad \left[\begin{matrix} n \\ k ...
-1
votes
3answers
60 views
Show that a finite domain is a division ring [duplicate]
Let $R$ be a finite ring. Show that the following are equivalent:
i. $R$ is a division ring.
ii. $R$ is nontrivial and if $r$,$s \in R$, with $rs=0$, then either $r=0$ or $s=0$.
$\textbf{NOTE:}$ A ...
1
vote
1answer
44 views
What motivation for assuming field K is infinite.
A theorem in Shaum's Outline of Linear Algebra says that if we suppose the field $K$ is infinite then any system of linear equations has either a unique solution, or no solution, or an infinite number ...
1
vote
1answer
34 views
Contradiction with Nth roots on finite fields
I am having problems finding the mistake in my thought process here. One of the results from Ireland-Rosen on the topic:
If $F$ is a finite field with $q$ elements then for every $\alpha \in F^*$ , $...
0
votes
1answer
48 views
Prime of the form $n^2-2m^2$
I need to prove that a prime $p$ is of the form $n^2-2m^2$ iff $p=2$ or $p=8k\pm 1$. So first I tried figuring out, for which $p$ does $n^2-2m^2=0$ has a solution if $\mathbb{F}_p$, or similarly all ...
1
vote
1answer
39 views
Squares in a finite field $\mathbb{F}_p$
I need to find all prime $p$ s.t $n+3$ is the inverse of $n-3$ in $\mathbb{F}_p$. So obviously this means $(n+3)(n-3)=1\mod p$, meaning $n^2=10\mod p$. So the question is - for which $p$ does the ...
0
votes
1answer
73 views
Definition of Frobenius automorphism
I quote the following problem from the chapter Hilbert's Ramification Theory of Jurgen Neukirch
Let $L/K$ is a Galois extension with prime ideal $\mathfrak{P}$, unramified over $K$, then there is one ...
4
votes
1answer
90 views
An isomorphism between two finite fields
Suppose we have two fields $F_1$ and $F_2$ of order $9$ where both groups of units are cyclic, i.e. $$F_1=\{0\}\cup\{\alpha^i\,|\,0\leq i\leq 7\},\qquad F_2=\{0\}\cup\{\beta^i\,|\,0\leq i\leq 7\}$$ ...
6
votes
1answer
136 views
The splitting field of polynomial over $Z/2Z$
I am trying to figure out the splitting field of $x^4 ļ¼ x^3 + 1$ over $\mathbb{F}_2$ .
I know $x^4 ļ¼ x^3 + 1$ over $\mathbb{F}_ļ¼$ is irreducible.
Let $α$ be a root of $x^4 ļ¼ x^3 + 1$, then the ...
2
votes
1answer
53 views
multiply and sum in Finite Field
$F_q$ is a finite field of $q$ (which equals $p^n$ļ¼p is a prime number). $F_q^*$ denotes the elements in $F_q$ which has inverse.
Prove that:
The multiply of all the elements in $F_q^*$ equals -1.
$pļ¼...
1
vote
0answers
35 views
If $f(x)=ax^{2p}+bx^p+c\in\mathbb{F}_p[x]$, prove that $f'(x)=0$
If $R$ is a commutative ring, then the set of all polynomials with coefficients in $R$ is denoted by $R[x]$.
$\mathbb{I}_p[m]$ is the integers mod $m$.
When $p$ is a prime, we will usually denote the ...
3
votes
1answer
27 views
Union of all finite fields of order $p^i$, for some prime number $p$ is algebraically closed. [duplicate]
Let $p$ be a prime number. Consider for all $k,r\in\mathbb{N}_0$ with $k|r$ the field $\mathbb{F}_{p^k}$ as a subfield of $\mathbb{F}_{p^r}$. Define
$$ \overline{\mathbb{F}_p}:=\bigcup_{i\in\mathbb{N}...
2
votes
0answers
33 views
When is a two-dimensional representation of a finite group over a finite field defined over a subfield?
I'm reading the proof of the Deligne-Serre theorem attaching Galois representations to newforms of weight one, and there's a representation-theoretic argument that I don't understand at all.
The setup ...
2
votes
1answer
22 views
Prove or confute the follow proposition
I have to prove or confute the follow proposition:
Let $F$ a field and $ f: $$\mathbb Z \rightarrow F$ an homomorphism of rings such that $f(1_\mathbb Z ) =1_F$.
If $f$ isn't injective $\Rightarrow$ $...
2
votes
0answers
40 views
Galois covers of curves of arbitrary degree.
For smooth projective algebraic curves over finite fields. Do they admit a finite Galois cover of any degree, that is not induced by just base extension?
0
votes
3answers
39 views
How to calculate with $\mathbb{Z}/2\mathbb{Z}$ with an unknown variable?
When calculating with numbers from a $\mathbb{Z}/2\mathbb{Z}$ how do you deal with unknown variables? For example, if I have the following term:
$(a - 1)(a - 1) - (a - 1) - (a - 1) = a^2 + 1$
Or is ...
3
votes
1answer
57 views
Find the field that $\mathbb{Z}_7[x,y]/\langle y-2x^2, 4xy + y +1 \rangle$ is isomorphic to
See the title. Here the set $\mathbb{Z}_7 = \{0,1,2,3,4,5,6\}$ is considered a ring with the obvious operations $+$ and $\cdot$; and $I := \langle y-2x^2, 4xy + y + 1 \rangle$ is an ideal in $\mathbb{...
0
votes
0answers
56 views
How many morphism $\mathbb{F}_q\to \mathbb{F}_{q^n}$
Sorry for my bad English.
Let $q$ be prime $p$ power, and $n>0$ be integer, and $\mathbb{F}_q$, $\mathbb{F}_{q^n}$ be finite fields.
Now how many morphisms of field $\mathbb{F}_q\to \mathbb{F}_{q^n}...
0
votes
1answer
31 views
If $f$ is not injective then $F$ is finite.
I have to prove or confute the follow proposition:
Let $F$ a Field and $f:\mathbb{Z} \to F$ an homomorphism of rings such that $f(1_\mathbb{Z})=1_F$. Show that if $f$ isn't injective then $F$ is ...