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)$.
5,062
questions
-4
votes
0
answers
25
views
Which is the characteristic of a field K? [closed]
Calculate the characteristic of a field K knowing that $x^4 = x$ for each x $\in$ K.
- 1
1
vote
1
answer
27
views
Determining the distance of linear code using parity-check matrix
A matrix $H$ over $\Bbb F_2$ has as the first seven rows $I_7$ and the other rows are all of the vectors of $\{0,1\}^7$ with exactly three $1$'s per vector (weight-$3$ vectors). I know that this can ...
- 1,634
0
votes
0
answers
21
views
Finding LFSR periods
We have LFSR with corresponding linear automata $A \in F_2^{n\times n}, B \in F_2^n$. We know that this LFSR's generating function is $B^T * (A - I_n * x)^{-1} * S$, where $S$ is the state from $F_2^n$...
- 71
1
vote
1
answer
27
views
Characterization of an irreducible polynomial mod p
Let $p$ be an odd prime, and let $n=p^k$ where $k\ge 1$. Define
$P_n$ to be the set of non-zero polynomials of degree at most $k-1$
and coefficients in $[0,p-1]$. Thus $|P_n|=n-1$.
Now let $f$ be a ...
- 413
5
votes
1
answer
60
views
Orders of all the elements in polynomial quotient ring
Consider a quotient ring $\dfrac{F_p[x]}{(f)}$, where $p$ is prime. I want to find all the possible orders in this ring.
I know that with given factorization of $f(x) = f_1(x)^{k_1} * ... * f_n(x)^{...
- 71
5
votes
2
answers
70
views
For multiplications over a finite field, what happens to the elements which, after modulo the reducing polynomial, still don't fit in the field?
To the best of my understanding, performing multiplication over finite-field elements looks like:
Multiply the elements together in their polynomial representation; and then
if the resulting ...
- 55
0
votes
0
answers
31
views
How can they use a solved irreducible to factor a polynomial? [closed]
I am having difficulty understanding a concept in a Galois field, at an introductory level.
I am using the book "Error Control Coding: Fundamentals and Applications" by Shu Lin and Daniel ...
- 141
0
votes
0
answers
44
views
Finding small root of $y = ax + b$ over a finite field
Take $a, b \in \mathbb Z / p\mathbb Z$, $p$ being a large prime number.
Suppose there exists a small root $(x, y)$, $x = O(\sqrt p)$ and $y = O(\sqrt p)$ to the equation $y = ax + b \mod p$.
How could ...
1
vote
1
answer
30
views
Question on smooth affine curves over finite fields and Hasse-Weil [closed]
I don't have a strong background in algebraic geometry, so my question could seems trivial, but I would like to know more about it. So if you have a book to recomend, thanks in advance!
Suppose you ...
- 11
2
votes
0
answers
69
views
Counting mutually annihilating matrices over finite fields
Let $q=p^n$ and let $A,B$ be two $n \times n$ matrices over $\mathbb{F}_q$ such that $AB=BA=0_n$.
Let $0 \leq k \leq n$ be the nullity of a fixed $A$ (i.e. the dimension of the nullspace $\ker A$, of $...
- 235
0
votes
0
answers
17
views
How to use the automorphism of extended field to represent the elements of subfield?
how to prove the content of the red line?
$Z,Z(a)$are finite fields
- 39
0
votes
1
answer
69
views
Proving this polynomial is in $ K[X]$
This appears in a bigger context, but in summary, I have $K\subset L$ extension of finite fields and $\alpha\in L$ such that $L=K(\alpha)$. Also, $G=Aut_K L$. Now, I need to prove the following:
$$f_K^...
- 77
0
votes
0
answers
34
views
Vandermonde submatrix corresponding to $n$th roots of unity and efficiently solving linear system of equations
Let $n>k$, $n|q-1$. We have an $k*k$ linear system of equations $Ax=b$ over a finite field $\mathbb{F}_q$. Matrix $A$ is full rank and it is a submatrix of Vandermonde matrix $V$ corresponding to $...
- 41
0
votes
1
answer
67
views
Why doesn't linearity of squaring over Galois Field imply linearity of cubing?
I am reading through this paper and in $\S$3.3 it describes how for $GF(2^{128})$ it is easy to show that squaring is linear, i.e. because the field is of characteristic 2 so the cross term vanishes. ...
- 55
0
votes
1
answer
44
views
Every field extension of a finite field is separable? [closed]
I understand this is true if our extension is finite, but is it true in the general case where we have no restriction on the order of the field extension? I know how to prove that every element of ...
1
vote
1
answer
45
views
Generating de Bruijn sequence over Galois fields using primitive polynomial
This question is related to Greg Slodkowicz's question and the discussion about this paper.
We define a de Bruijn sequence of order $k$ over the set of $l$ distinct symbols as a cyclic sequence of ...
- 11
5
votes
1
answer
233
views
number of rational points of hyper elliptic curve $y^5=-x^2+x$ over $\Bbb{F}_{121}$
Let $C$ be a curve given by $y^5=-x^2+x$ defined over $\overline{\Bbb{F}_{11}}$.
I want to calculate $\# C(\Bbb{F}_{11})$ and $\# C(\Bbb{F}_{11^2})$.
I calculated $\# C(\Bbb{F}_{11})＝\#\{(0,0),(1,0),(...
- 4,315
0
votes
0
answers
26
views
Minimum polynomial of generator of finite extension
Let $K\subset L$ be an extension of finite fields and $G=Aut_K L$. Prove: for $\alpha\in L$ with $L=K(\alpha)$, we have
$$f_K^{\alpha}= \prod_{\sigma\in G} (X-\sigma(\alpha)) $$
What is the ...
- 77
0
votes
0
answers
32
views
How to prove set of all separable elements is a subfield?
If K is a finite extension in a char p field, how do we prove that the set of all separable elements in K is a subfield? I've tried working with the tower law for field extensions, but I'm not really ...
1
vote
0
answers
31
views
Rank over $\mathbb F_p$ compared to rank over $\mathbb R$.
I'm looking at the rank of certain square matrices given some constraints on the entries. The matrix entries are in $\mathbb Z_p$, and I want to minimize the rank under some conditions.
Suppose I know ...
- 1,478
2
votes
2
answers
76
views
Polynomial irreducibility over $\mathbb{F} _{7^n}$
I recently came across this question from a while ago.
In it, an affirmation is made: The smallest extension of $\mathbb{F}_7$ in which an irreducible cubic polynomial has a root is $\mathbb{F}_{7^3}$....
- 77
4
votes
1
answer
66
views
Structural description for the order of $\mathrm{GL}_n(\mathbb F_q)$
This question is inspired by the cute answer to Order of general- and special linear groups over finite fields.
The formula
$$
|\mathrm{GL}_n(\mathbb F_q)|=q^{\frac{n(n-1)}2}(q-1)(q^2-1)\cdots(q^n-1).
...
- 1,533
0
votes
0
answers
44
views
Using quadratic extensions, show that there is only one field of order $p^2$ for an odd prime $p$.
I understand that this result has been proven before, but I am trying to prove it in another way that I can't seem to find on SE.
The question goes as follows:
Let $E$ be a quadratic extension of a ...
- 509
0
votes
0
answers
39
views
Monomial permutation polynomial [duplicate]
https://arxiv.org/pdf/1211.6044.pdf Theorem 1.14 (2):
The monomial $x^n$ is a permutation polynomial of $F_q$ if and only if $gcd(n, q − 1) = 1$.
Let's pick $n=2$ and $q=6$ so $gcd(2,5) = 1$ in this ...
- 41
0
votes
0
answers
67
views
Irreducible polynomial in $\mathbb{F}_2$
Let $t$ a transcendental element on $\mathbb{F}_2$. Prove that $f(x)=x^3-t^3$ is irreducible in $\mathbb{F}_2(t^3)[x]$.
If $f$ is reducible, then we have a solution of $x^3-t^3$, we can call it $\...
- 314
0
votes
0
answers
19
views
Subset sum problem with fixed linear constraints
I am currently troubled by a problem that seems to be a generalization of the NP-hard subset sum problem over a finite field $\mathbb{F}$. For simplicity, let's assume $\mathbb{F}$ is of a large prime ...
- 131
1
vote
1
answer
50
views
Finding ${\rm Aut}_{\mathbb{F}_{27}}(\mathbb{F}_{19683})$
I have to find the set of $\mathbb{F}_{27}$-Automorphisms of $\mathbb{F}_{19683}$, where $\mathbb{F}_n:=\mathbb{Z}/\mathbb{Z}_n$.
I know that since $27=3^3$ and $19683=3^9$ and $3\vert{9}$, there ...
- 51
0
votes
0
answers
46
views
Determining the degrees of the irreducible factors of $X^{19}-1$
I'm trying to find the degrees of the irreducible factors of $X^{19}-1$ in $\mathbb{F}_7[X]$ and $\mathbb{F}_{7^3}[X]$.
I'm really struggling with how to approach this question. I did notice that $X^{...
3
votes
0
answers
35
views
Examples of Clifford algebras over finite fields
Yesterday I was in a discussion about solving an applied problem using clifford algebras over a finite field. While this is not (seemingly) disallowed by the definition of a clifford algebra (which ...
- 131
0
votes
0
answers
31
views
Can Fast Fourier Transform (FFT) be implemented using Clifford Algebra over GF(3)?
Background. Fast Fourier Transform (FFT) is an algorithm used to quickly calculate the discrete Fourier transform (DFT) of a sequence. It is widely used in signal processing, image analysis, and data ...
- 1,157
0
votes
0
answers
80
views
Normal basis on tower | composite fields
I'm trying to help someone with normal basis tower fields, specifically for isomorphic mapping of $GF(2^8)$ to $GF(((2^2)^2)^2)$. At the time I originally posted this question, I was familiar with ...
- 486
1
vote
1
answer
40
views
$\mathfrak{B}=((1,2,0)^t ,(2,1,2)^t ,(3,1,1)^t)$ is a basis of $\mathbb{R}^3$. For what prime numbers p is $\mathfrak{B}$ a basis of $\mathbb{F}^3_p$?
I'm not quite sure, but it seems to me that $\mathbb{F}^3_p$ is the finite field in three dimensions with $p$ elements inside it, where $p$ is the prime number(s) we are looking for. A finite field is ...
- 349
1
vote
1
answer
36
views
Let $V = \mathbb F_p^9$ and $W \subset V$ a dimension $5$ subspace. Find the number of subspaces $U \subset V$ with $\dim(U) = 6, \dim(W \cap U) = 3$
Let $K = \mathbb F_p$ be a finite field with $p$ elements where $p$ is a prime Let $V = K^9$ be a vector space, and let $W \subset V$ be a subspace of $V$ such that $\dim(W) = 5$. Find the number of ...
- 2,981
0
votes
0
answers
29
views
Enumerating monomorphisms of finite-dimensional $\mathbb{F}_2$-algebras
I want to enumerate the monomorphisms of finite-dimensional $\mathbb{F}_2$-algebras.
Of course, each such monomorphism is a linear map between finite-dimensional $\mathbb{F}_2$-vector spaces, and so ...
- 3,050
-1
votes
0
answers
29
views
Non-identically zero polynomials of degree $n$ over $\mathbb{F}_n$
Let $\mathbb{F}_n$ be a finite field, and $X \subset \mathbb{F}_n^n$ be of size $2^n - 1$. Must there exist $P$ such that
$P \in \mathbb{F}_n[x_1, ..., x_n]$,
$P$ is of degree $n$,
$P$ is zero on $X$,...
- 265
0
votes
0
answers
20
views
Given a support set calculating Walsh transform.
I have support set of length 120 of a bent function over $GF(256)$.
$GF(256)=<\beta>$ is generated by the polynomial $x^8+ x^4 + x^3 + x^2 + 1$. The support set is of the form
{$\alpha 0 1 0$, $\...
- 77
2
votes
0
answers
67
views
Is the absolute trace of $\frac{xy}{(x+y^4)^2}$ equal to zero?
Let $\mathbb{F}_{q}$ with $q=2^m$ be the finite field of $q$ elements. Let $x,y \in \mathbb{F}_{q}$. Let $m$ be any integer. If $xy(x+y)=1$ and $x+y^4\neq 0$, then experiment data for $m=3,4,5,6,7,...
- 141
1
vote
2
answers
169
views
Largest number of shards for linear erasure codes over a finite field
I'm wondering about the largest linear erasure codes you can make given that shards are an elements of a particular finite field.
If you have $D$ data shards and $P$ parity shards, and a finite field $...
- 345
1
vote
1
answer
44
views
is there a ring map from $\mathbb{Z}[e^{2\pi i/(p-1)}]$ to $\mathbb{Z}$ mod p where p prime?
I have learned about splitting fields and finite fields and some related concepts from my maths courses and I got suspicious that $F_p$ can be though of as not just as splitting field for $x^{p-1} - 1$...
0
votes
0
answers
19
views
Decomposition of Galois group into direct product using the main theorem
I have a question concerning the main theorem of Galois theory: If $K$ is a field with finite Galois extensions $M,Z$, so that $K\subset M\subset Z$, the theorem says that $$Gal(Z/K)/Gal(Z/M)\cong Gal(...
- 41
0
votes
0
answers
35
views
BCH Code generator polynomial
I understood that for BCH codes the native approach to get a generator polynomial over $\text{GF}(q)$ with root $\alpha$ and ability of correcting $t$ errors
$$g(x) = (x - \alpha)...(x-\alpha^{2t})$$ ...
- 133
2
votes
2
answers
32
views
In a finite field $GF(p^n)$, is it true that $a^{1 + p + p^2 + ... + p^{n-1}}$ always belongs to $GF(p)$?
Consider a finite field $F = GF({p^n})$, and $a \in F$ with $a \not = 0$.
How can we prove that $a^{1 + p + p^2 + ... + p^{n-1}}$ belongs to $GF(p)$?
This is a key fact of Itoh-Tsujii algorithm, but I ...
- 203
0
votes
1
answer
92
views
XOR-Product Modulo Prime
Every natural number seems to map to a polynomial in binary field GF(2). For example, $11 = 1011_2 \mapsto x^3 + x + 1$, and $x^3 + x + 1 \mid_{x=2}$ gives 11. How naturally can I go between natural ...
- 10.3k
3
votes
1
answer
84
views
Conditions on $K(X)/K(X^n)$ being Galois
Statement: $K(X)/K(X^n)$ is Galois if and only if $p$ doesn't divide $n$ and $K$ contains all the zeroes of the separable polynom $g := X^n-1 \in K[X]$. (the polynom is certainly separable because $p$ ...
- 347
0
votes
0
answers
23
views
Why is $\mathbb{F}_{p^r}$ the splitting field of the polynomial $X^{p^r-1}-1$? [duplicate]
Why is $\mathbb{F}_{p^r}$ the splitting field of the polynomial $X^{p^r-1}-1$? This is mentioned on my lecture notes but I don’t have a reference for this fact (and I couldn’t find it online).
- 39
-2
votes
1
answer
63
views
Issue with Elliptic Curve over finite field division
$G$ is the generator point, In spec256k1, I want to divide $5020G$ over $2$ which works and gives me a point where the scalar is $2510$. To do that I first find ...
user1142553
1
vote
2
answers
94
views
How to solve a system of equations over a finite field?
I need to solve a system of equations over $\mathbb{Z}_{11}$.
My system is:
$$ \left\{
\begin{array}{l}
2x + 5y + z = 8 \\
7x + 6y + 8z = 10 \\
10x + 3y + 4z = 6
\end{array}
\right.
$$
In matrix form:...
- 11
4
votes
1
answer
118
views
How large can $X\subset \mathbb{F}_2^{10}$ be without solutions to $x_1+\cdots+x_n=0$ for $n\le4$?
Suppose some 10-bit binary numbers, $X\subset \mathbb{F}_2^{10}$. I'd like to construct $X$ as large as possible with no solutions to $x_1+\cdots+x_n=0$ for $x_i\in X$ and $n\le 4$. Explicitly,
The ...
- 605
0
votes
1
answer
29
views
$(\mathbb{F}[T] \ / \ P^2 \mathbb{F}[T])^*$ cyclic if and only if $\text{deg}(P)=1$ where $P$ is an irreducible polynomial over a finite field [duplicate]
I am asked to prove that if $\mathbb{F}$ is a finite field of size $p$ prime and $P\in \mathbb{F}[T]$ is an irreducible polynomial over $\mathbb{F}$ then $(\mathbb{F}[T] \ / \ P^2 \mathbb{F}[T])^*$ is ...
0
votes
1
answer
66
views
Weird result in a finite field
Consider the field $\mathbb{Z}_{5}[x]_{x^2 + x + 1}$. In this field, the polynomial $x^3$ is equal to
$$
\begin{align}
x^3
&\equiv_{x^2 + x + 1} x^3 - x(x^2 + x + 1) \\
&\equiv_{x^2 + x + 1} x^...
- 174