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)

22
votes
0answers
367 views

Ring structure on the Galois group of a finite field

Let $F$ be a finite field. There is an isomorphism of topological groups $(\mathrm{Gal}(\overline{F}/F),\circ) \cong (\widehat{\mathbb{Z}},+)$. It follows that the Galois group carries the structure ...
12
votes
0answers
96 views

Related Forms for the Riemann Hypothesis over Finite Fields

There are several formulations and consequences of the Riemann Hypothesis for Curves over Finite Fields. I am interested in the logical implications between those, and in elementary (as possible) ...
11
votes
0answers
197 views

Subgroup structure of $\mathrm{SL}(2, p^2)$ and its irreducible characters

I am taking a course in representation theory of finite groups, and somehow I ended up getting assigned to write a report on subgroup structure and irreducible characters of $\mathrm{SL}(2,7)$ and $\...
10
votes
0answers
200 views

On the maximum number of polynomials in a certain subspace

I've already asked this question on mathoverflow, but no one answered. So I put this problem also here. Sorry for that. Let $\mathbb F_q$ be a finite field and let $e, k$ be positive integers with $...
7
votes
0answers
167 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 ...
7
votes
0answers
532 views

Hardness of finding eigenvalues over finite fields

How hard is it (computationally) to find eigenvalues/eigenvectors of matrices over finite fields? Suppose the field has size exponential in the input. (Does the QR algorithm still converge?) How ...
6
votes
0answers
134 views

Isomorphism between finite fields adjoining a root

Let $p(x)=x^3+x^2+1$ and $q(x)=x^3+x+1$ be polynomials over the field $\mathbb{Z}_2$. Let $\alpha$ be a root of $p(x)$ and $\beta$ be a root of $q(x)$. Now let $K=\mathbb{Z}_2(\alpha)$ and $F=\mathbb{...
5
votes
0answers
162 views

Spliting subspaces and finite fields

I'm sure that the following is true, but I can't prove it. Let $R<S<K, R=\mathrm{GF}(q),\ S= \mathrm{GF}(q^n), \ K= \mathrm{GF}(q^{mn})$ be a tower of finite fields and $A = \{\theta\in K: \...
5
votes
0answers
84 views

Why Fibonacci LFSR random number generation works?

If I use primitive polynomial of GF($2^m$) in Fibonacci LFSR, it is generating all m-length binary combinations. But, I cannot understand why this should happen. I am not getting any mathematical ...
5
votes
0answers
174 views

Find minimal set of cosets $C$, so that each $2$ vectors in $A_n$ are in one coset in $C$

Let $F_2^n$ be the set of all vectors of length $n$ with values of $0$ or $1$ and $A_n$ = $F_2^n \setminus(11\ldots1)$. Set $A_n$ contains all vectors except one with all $1$s. We can consider cosets ...
5
votes
0answers
186 views

Ultraproduct of the algebraic closure of finite fields

Ok, I have done a little research on the next problem, and there are simple proofs of it using model theory, logic and the Łoś's theorem. But here, the idea is to prove it using only Field Theory, ...
5
votes
0answers
125 views

Irreducible polynomials of degree $d$ such that $[x]$ generates $\mathbf{F}_{p^d}^{\times}$

It is often convenient to represent the field $\mathbf{F}_{p^d}$ as $\mathbf{F}_p[x]/(f(x))$, where $f$ is irreducible with degree $d$, $f$ has just a few nonzero terms, and $[x]$ itself is the ...
4
votes
0answers
70 views

Multiplicative group of $\mathbb{Z}/p\mathbb{Z}$ for a prime $p$ is cyclic

This question has been explored thoroughly, and in more generality too. For general fields, I am aware of standard proofs. However, I was naively trying to prove it in the simple case of prime $p$ ...
4
votes
0answers
37 views

The Cardinality of a subset of field of 8 elements

Let $F$ be a field of $8$ elements. Let $A$ be a subset of $F$ and $A = \{x \in F \mid x^7=1$ and $x^k \neq 1$ for $k<7\}$. Then find the number of elements in $A$. Argument: Since $F$ is a ...
4
votes
0answers
99 views

Number of $\mathbb{F}_q$-rational points on a smooth variety

From the proof of Weil's conjectures it follows that $|q^k - \# X(\mathbb{F}_{q^k})| = O(q^{k(n - \frac{1}{2})})$, where $X$ is a smooth variety over $\mathbb{F}_q$ and $n = \dim X$ (see for example ...
4
votes
0answers
50 views

Moments of the number of roots of polynomials over finite fields

Let $F:=\{f\in\mathbb{F}_q[X_1,\ldots,X_n]: \textrm{deg}(f)\leq d\}$ be the set containing all $n$-variate polynomials of degree less than or equal to $d$ over finite field $\mathbb{F}_q$ of prime ...
4
votes
0answers
36 views

Finite Fields and Discrete Log Problem

The finite field $\mathbb F_{p^p}$, for a prime $p$, can be described as $\mathbb F_p[x]/(x^p−x−1)$. Let $G=\mathbb F_{p^p}^\times/\mathbb F_{p}^\times$. Estimate the cost of obtaining the discrete ...
4
votes
0answers
125 views

Finding zeta function of an elliptic curve

Let p=3 (mod 4) be a prime, and $E/F_{p^r}$ be the elliptic curve given by $y^2 = x^3 − x$ Find the zeta-function of $E/F_p$ and use it to determine $|E(F_{p^r} )|$ for all r>0.
4
votes
0answers
32 views

How to find the minimum polynomial over a Galois Field

How would I find the minimum polynomial $m_4(x)$ of $\xi^4$, where $\xi= x \pmod{x^6+x+1}$ in $GF(2^6)$? This is what I think I need to do so far: Let $\alpha=\xi^4$. Then I would find the conjugacy ...
4
votes
0answers
69 views

Is there a recurrence formula for finding primitive polynomials in order to construct $\mathbb{F}_{p^n}$?

(In a previous question, I asked some related question but it was very disorientingly formulated. I apologize for that.) Let $p$ be a prime and $n\geq 1$ an integer. The finite field $\mathbb{F}_{p^n}...
4
votes
0answers
59 views

Blocking set for cosets of codimension $2$

In this paper following theorem is proved: If $V$ is vector space of dimension $n$ over a finite field $F$ of $q$ elements then any subset of $V$ which meets every hyperplane of $V$ contains at least ...
4
votes
0answers
112 views

Multiplicative subgroup of a finite field with prescribed trace.

Any suggestions/methods/estimates for the following problem would be very appreciated. $l,p$ are primes with $p \equiv 1 \!\! \pmod l$. $r$ is a positive integer with $r \equiv 1 \!\! \pmod p$ and $q ...
4
votes
0answers
726 views

The automorphism group of a field with $p^2$ elements

Suppose $K$ is a field. Then we call $f: K\to K$ a (field) automorphism if $f$ is a one-to-one, onto and unital (i.e. $f(1)=1$) homomorphism of rings. The following results are well-known. There ...
4
votes
0answers
1k views

How can I solve system of linear equations over finite fields in WolframAlpha?

Is it possible to solve system of linear equations over finite fields using Wolfram Alpha? If yes, how can I do that? Let us take a system $x+y+z=0$, $2x+y+2z=0$, $x+3y+z=0$. If I want to solve this ...
4
votes
0answers
762 views

Minimal polynomial of a finite purely inseparable field extension

Given $F$, a field with characteristic $p > 0$, and a finite purely inseparable field extension $E$. Then prove that the minimal polynomial $f(x)$ of any $\alpha \in E\backslash F$ will be of the ...
3
votes
0answers
24 views

Show $|E_1(\mathbb{F_q})|+|E_2(\mathbb{F_q})|=2(q+1)$

...under the assumption that $E_1,E_2$ are elliptic curves over $\mathbb{F_q}$ and that there is a (surjective) isogeny $\pi:E_1\rightarrow E_2$ defined over $\mathbb{F_{q^2}}$ obeying $\pi\phi_1=-\...
3
votes
0answers
46 views

There is no irreducible polynomial of largest degree in $\mathbf{F}_q[x]$

I am asked to prove or disprove that given a finite field $\mathbf{F}_q$, the ring $\mathbf{F}_q[x]$ contains irreducible polynomials of arbitrarily large degree. I couldn't think of a reason why this ...
3
votes
0answers
21 views

finite fields: efficient primitive element test?

Suppose $x \in F_n^{*}$, where $F_n$ is a finite field. Is there an efficient way to test whether x is a primitive element? This is the best I can come up with: You factor n-1 into all of its factors,...
3
votes
0answers
39 views

a symmetric matrix over GF(2)

let $A$ be a symmetric $n$ by $n$ matrix over $\mathbb{GF}(2)$. Using elementary linear algebra, it is quite easy to show that diag $A$ is in the range of $A$, where diag $A = [a_{11},a_{22}, \dots, ...
3
votes
0answers
152 views

Irreducibility of a polynomial modulo infinitely many primes

Suppose $f(x) \in \mathbb{Z}[x]$ is an irreducible monic polynomial over $\mathbb{Q}(\alpha)$ of degree $n$, where $\alpha$ is a root of a monic polynomial $g(x) \in \mathbb{Z}[x]$. Assume that the ...
3
votes
0answers
42 views

Number of square-free polynomials over a finite field - a combinatorial interpretation?

One can show using zeta functions that the number of (monic)square-free polynomials of degree $n$ over a finite field $\Bbb F_q$ is $q^n-q^{n-1}$. For instance, this is done here. The answer is ...
3
votes
0answers
25 views

Twisted Kloosterman Sums

A twisted Kloosterman sum is a character sum of the form $$S(\chi, \psi, \eta)=\sum_{t\in (\mathbb{F}_q)^{\times}} \chi(t) \psi(t) \eta(t^{-1}).$$ Here, $\chi$ is a multiplitive character of $(\mathbb{...
3
votes
0answers
59 views

Are two dot products of a random variable vector independent?

Let $w,v$ be two different vectors in the finite vector space $Z_p^m$ over $Z_p$ where $p$ is prime. Let $u$ be a vector chosen uniformly at random from $Z_p^m$. Are the random variables $u \cdot w$ ...
3
votes
0answers
49 views

Why is the image of a $\pmod p$ Galois representation finite?

Let $\overline{\mathbb{F}_q}$ be the algebraic closure of the finite field on $q=p^r$ elements, and $\text{Gal}(\overline{\mathbb{Q}}/\mathbb{Q})$ the absolute Galois group with the profinite topology....
3
votes
0answers
43 views

Additive character sum over intersection of additive and multiplicative subgroups of finite fields

Let $H$ be a multiplicative subgroup of the finite field $\mathbb{F}_q$ with $q$ elements, say $H$ is the subgroup of $d$-th powers, $d \mid q-1$. Let $L$ be a subspace of $\mathbb{F}_q$ over some ...
3
votes
0answers
63 views

Let $K$ be a field. Prove that $K(X,Y)$ is a finite extension of $K(X^2,Y^2)$ and find its degree.

I conjectured that $K(X,Y)=K(X^2,Y^2)[X,Y]$ but to prove that I need to show $K(X,Y)\subset K(X^2,Y^2)[X,Y]$. I'm having problems showing any element in $K(X,Y)$ is of the form $X^mY^nF$ where $F\in K(...
3
votes
0answers
65 views

Working in a field.

When I calculate vector spaces, diagonalization of matrices, linear transformations on a field, can I work in $\mathbb R$ and ultimately transform the result to that field? For example if I calculate ...
3
votes
0answers
40 views

Extending Semilinear Transformations over Finite Fields

Suppose $ p $ a prime integer and $ m $ and $ n $ positive integers, where $ m | n $. Let $ \Phi_{m} $ denote the Frobenius automorphism of $ \mathbb{F}_{p^m} $ and $ \Phi_{n} $ the Frobenius ...
3
votes
0answers
49 views

Gram-Schmidt in characteristic two?

I was helping someone work on a computing problem with bit vectors that reduced to finding a basis knowing a spanning set, and realized quickly that the Gram-Schmidt process does not work as expected ...
3
votes
0answers
54 views

On the existence of a polynomial in several variables with only one zero

Given an ordered field $\mathbb{K}$, then for all $n>1$ there exists $f\in\mathbb{K}[X_1,\ldots,X_n]\ s.t.\ \mathcal{V}^{\mathbb{K}^n}(f):=\{p\in\mathbb{K}^n:f(p)=0\}=\{(0,\ldots,0)\}$ For ...
3
votes
0answers
124 views

Matrix which is not similar to it's transposed

Let $V$ be vector space over a field $\mathbb{k}$. I can prove that any matrix is similar to its matrix transpose if $\mathbb{k}$ is an infinite field, but is this still true when $\Bbb k$ is finite? ...
3
votes
0answers
45 views

Finite field question involving the trace and a permutation.

Let $q$ be a power of a prime $p$, and $m,l$ positive integers with gcd$(l,q^m-1)=1$. Denote $Tr$ to be the trace of $GF(q^m)$ over $GF(q)$. Suppose that there exists a nonzero $\gamma \in GF(q^m)$ ...
3
votes
0answers
92 views

Can we give efficiently the solution of a system of bilinear equations over a finite field?

Consider a finite field $F$ and suppose we have a system of equations $$h_1(\alpha,\beta)=0,h_2(\alpha,\beta)=0,...,h_t(\alpha,\beta)=0$$ where $\alpha=(\alpha_1,...,\alpha_s)$ and $\beta=(\beta_1,.....
3
votes
0answers
313 views

Prove that $x^{p^n} -x +1$ is irreducible over $\mathbb{F_p}$ only when n=1 or n=p=2

Question:Prove that $x^{p^n} -x +1$ is irreducible over $\mathbb{F_p}$ only when n=1 or n=p=2 I know it is a duplicate question. However, someone gave some nice hints on this problem and I want to ...
3
votes
0answers
161 views

When is a generalized Vandermonde matrix over a finite field invertible?

The generalized Vandermonde matrix that I am considering is one where the rows of a matrix correspond to the powers of different elements of the field, but the powers need not be consecutive integers ...
3
votes
0answers
155 views

On polynomials over finite fields?

Pick prime $q\in\Bbb Z$ such that $q>B^{3t}>(mB)^{2t}$. Suppose I have a multilinear polynomial $g(x)\in \Bbb Z[x_1,\dots,x_n]$ of degree $t$ with $m^t$ non-zero coefficients that bound by $|B|&...
3
votes
0answers
39 views

Irreducible representations of inhomogeneous linear transformations over $\mathbb{F}_q$

Let $\mathbb{F}_q$ be a finite field with $q$ elements and let $G$ be the group of inhomogeneous linear transformations over $\mathbb{F}_q$, that is $x\mapsto ax+b$ for some $a\in \mathbb{F}_q^*$ and $...
3
votes
0answers
42 views

Discrete Fourier Transform of a shift of a tuple over a finite field

Let $a = a_0 a_1 \cdots a_{N-1}$ be a sequence over a finite field $\mathbb{F}_q$, where $N \mid q^n-1$ for some $n$. Let $\xi_N$ be a primitive $N$-th root of unity in the extension $\mathbb{F}_{q^n}$...
3
votes
0answers
92 views

Splitting field in finite field

What is the splitting field of the polynomial $X^{p^8}-1$ over $\mathbf F_p$? I'm confused, is not $X^{p^8}-1=(X-1)^{p^8}$ then the splitting field is $\mathbf F_p$? Thanks.
3
votes
0answers
98 views

zeros of a simple polynomial

For $x, y \in GF[2^n]$, consider the two-parameter polynomial $P(x,y) = x \cdot y + f(x) + g(y)$, where $f$ and $g$ are arbitrary polynomials on $GF[2^n]$. Can we say anything about the number of ...