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,550 questions
2
votes
1
answer
47
views
How to count the number of monic polynomials of degree $n$ over $F_q$ without repeated roots?
It's easy to count the number of monic polynomials of degree $n$ over $F_q$ without repeated roots using the following code (e.g., q = 3, n = 4):
...
- 23
-2
votes
0
answers
26
views
How many consistent(Q(x),E(x)) pairs exist in the Berlekamp-Welch algorithm with ℓ≤k errors? [closed]
Let P(x) be a degree-d=n−1. polynomial over GF(p), where p is prime. Suppose we are given n+2k points (xi,yi), of which exactly ℓ≤k are erroneous
The Berlekamp-Welch decoding algorithm seeks ...
- 1
2
votes
0
answers
63
views
A polynomial $f(x)$ has a root over $\mathbb{F}_p$ for each $p$ but has not root over $\mathbb{Q}$ [duplicate]
I found the following question in S.-T. Yau College Student Mathematics Contest 2013:
Find a polynomial $f(x)$ with integer coefficients which has a root over $\mathbb{F}_p$ for each prime $p$ but ...
- 57
-2
votes
0
answers
48
views
Show that every element in a finite field is a sum of two squares. [closed]
Show that every element in a finite field is a sum of two squares.
I am solving Fields and Galois theory by Patrick Morandi. This is in the chapter of finite fields.
- 11
2
votes
1
answer
58
views
Range of the trace map on elliptic curves
For an elliptic curve $E/{\mathbb F}_q$, let $\pi_q$ be the Frobenius endomorphism and define the trace map $\mbox{Tr}: E({\mathbb F}_{q^k}) \rightarrow E({\mathbb F}_{q^k})$ by $\mbox{Tr}(P) = \sum_{...
- 739
5
votes
0
answers
51
views
Sum of squares in $\mathbb{F}_p[T]$
A well-known formula by Jacobi says that the number of ways to express a given number as a sum of two squares is
$$
r_2(n) = 4 \sum_{2 \nmid d | n} (-1)^{(d-1) / 2}
$$
which also gives a short proof ...
- 15.7k
0
votes
0
answers
50
views
Efficient matrix inversion over $\mathrm{GF}(2)$
Is there an efficient way to find the inverse of an invertible square matrix over $\mathrm{GF}(2)$ (the binary field)? That is, something more efficient than Gaussian elimination.
I've tried looking ...
- 105
2
votes
0
answers
42
views
A question about probability and polynomial over finite field
Let $f(x) \in \mathbb{Z}_p[x]$ be a polynomial of degree at most $N$, where $p$ is a prime and $N \mid (p - 1)$. The coefficients of $f(x)$ are restricted to the set $\{0, 1, -1\}$, with exactly $d + ...
- 53
3
votes
1
answer
54
views
Prove that $\sum_{a\in \text{GF}(p^t)}\omega^{\text{Tr}(ax)}=0$ when $x\in \text{GF}(p^{2t})\setminus \text{GF}(p^t)$
$\text{GF}(q)$ means the finite field with $q$ elements. The trace $\text{Tr}:\text{GF}(p^{2t})\to \text{GF}(p)$ is defined as
$$\text{Tr}(x)=x+x^{p}+x^{p^2}+\cdots+x^{p^{2t-1}}.$$
I want to prove ...
- 133
2
votes
1
answer
150
views
(Why) is this determinant null for every prime $p$?
This is a follow up question of this other of mine.
Let $p$ be a prime. For every $i,j\in\{1,\dots,p-1\}$, there is unique $k_{ij}\in\{1,\dots,p-1\}$ such that $\varphi_{k_{ij}}(i)=j$$^\dagger$. ...
- 4,405
1
vote
0
answers
22
views
Can we use the Plotkin construction for quasi-cyclic/constacyclic codes over $\mathbb{F}_2$ of even length?
For binary cyclic codes $C$ of even length $2n$, we can use Van Lint's construction to analyse its properties. In particular, for codes with generator matrix $g_1^2(x)g_2(x)$, we can look at two ...
- 227
7
votes
2
answers
588
views
Finite Fields in Coding Theory
I have a reasonable understanding of finite fields. But I have a few questions in this part I came across in a Coding Theory Book.
The Book is Coding Theory, A First Course by San Ling & Chaoping ...
- 662
0
votes
1
answer
40
views
The Probability of Getting $(n-1)$ Linearly Independent Vectors in Simon’s Algorithm After $M$ Measurements?
In Simon's algorithm, after running the quantum circuit, you get measurement results (bitstrings) that are orthogonal to a hidden string $s \neq 0$, an $n$-bit string. That means all the measurement ...
- 1,178
1
vote
0
answers
54
views
Literature on Jet spaces of polynomials over finite fields
I'm hunting for literature regarding jets of polynomials over finite fields / fields of positive characteristic. Characterizations of Cartan-Kahler type theorems and/or versions of prolongation theory/...
0
votes
0
answers
52
views
fields whose finite extension is always normal
Let $K$ be a field. I would like to characterize $K$ for which every algebraic extension is normal.
It is easy to see that if $K$ is finite(Prove that every extension of a finite field is normal), ...
- 337