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
-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$...
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 ...
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)^{...
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 ...
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 ...
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 ...
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 $...
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
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. ...
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). ...
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 ...
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 ...
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$, $\...
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 ...
user avatar
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 ...
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^...

1
2 3 4 5
102