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)

21
votes
0answers
297 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 ...
11
votes
0answers
190 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
188 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
112 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 ...
6
votes
0answers
117 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 ...
6
votes
0answers
518 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 ...
5
votes
0answers
68 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
171 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
121 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 ...
5
votes
0answers
144 views

Proof that $t^8+2t^6+4t^4+t^2+1$ is reducible in $\mathbb{F}_p$

Prove that the polynomial $t^8+2t^6+4t^4+t^2+1$ is reducible in $\Bbb F_p$, for all $p\in \Bbb P$. Here are some examples: $t^8+2t^6+4t^4+t^2+1=(1 + t + t^4)^2\pmod{2}$ $t^8+2t^6+4t^4+t^2+1=(1 + t) (2 ...
4
votes
0answers
113 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
28 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
65 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 ...
4
votes
0answers
56 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
110 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
166 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, ...
4
votes
0answers
642 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
18 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 ...
3
votes
0answers
56 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
37 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 ...
3
votes
0answers
35 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
60 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 ...
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
35 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
41 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
44 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
104 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
40 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
240 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
127 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
147 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 ...
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
39 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 ...
3
votes
0answers
78 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
97 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 ...
3
votes
0answers
57 views

Determinant of a generalization of Moore matrices

The Moore matrix over $\mathbb{F}_q$ is the $n\times n$ matrix whose i'th row is: $a_i,a_i^q,a_i^{q^2},\dots,a_i^{q^{n-1}}$. The determinant of this matrix is the product of all linear combinations ...
3
votes
0answers
65 views

How to prove how many ireducible polynomials are in a polynomial ring over a finite field.

Can someone help me out with some problem concerning the cardinaliy of ireducible polynomials in $(\mathbb Z/p\mathbb Z)[x]$? Here first why the problem appeared, I want to prove that ...
3
votes
0answers
34 views

Action of $\mathbb{F}_{p^2}^\times/\mathbb{F}_{p}^\times$ on $P^1(\mathbb{F}_p)$

Let $p$ be prime. Let $\alpha$ be a generator of the finite field $\mathbb{F}_{p^2}$. So, $\mathbb{F}_{p^2}=\mathbb{F}_p[\alpha]$. Multiplication by $\alpha$ is an $\mathbb{F}_p$-linear operator on ...
3
votes
0answers
64 views

Set with roots of $x^{p^{q}}-x$ is $\mathrm{GF}(p^q)$?

If $\mathrm{GF}(2^6) = \mathbb{Z}_2 [x]/ (x^6 + x + 1)$ and $u$ is a generator with $o(u)= 63$ how do I show $\mathrm{GF}(2^3)=\{0,1, u^9, u^{18}, u^{27}, u^{36}, u^{45}, u^{54}\}$? Here's what I ...
3
votes
0answers
105 views

Question about why $x^{p^n}-x+1$ is irreducible over $\mathbb{F}_p$.

I'm trying to follow a solution I'm reading. The idea is to prove $x^{p^n}-x+1$ is irreducible over $\mathbb{F}_p$ when $n=1$ or $n=p=2$. The solution is as follows: If $x^{p^n}-x+1$ is ...
3
votes
0answers
598 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 ...
3
votes
0answers
249 views

Number of solutions to $x^2+y^2=1$ in a finite field?

This question is related to a simple case of a previous question: How many solutions are there for $$ x^2+y^2=1 $$ in a finite field $F_q$? The answer of the this question would give the ...
3
votes
0answers
424 views

Order of orthogonal groups over finite field

The wikipedia article gives a formula for calculating the order of an orthogonal group over finite filed $O(n,q)$: I don't see how I can get such formula. Can one come up with some references?
3
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 ...
3
votes
0answers
91 views

Deligne and the four Weil statements about polynomials over finite fields?

This article mentions he recently won 3 million of some money. Does anyone have a link to the original Deligne paper that proves this, and could anyone give a basic rundown of how "counting points on ...
3
votes
0answers
135 views

when do two rational elliptic curves have identical size when reduced mod $p$ for all primes $p$?

If $E_1$ and $E_2$ are two elliptic curves over $\mathbb{Q}$ such that $|E_1(\mathbb{F}_p)|=|E_2(\mathbb{F}_p)|$ for all primes $p$, what does this tell us about the relationship between $E_1$ and ...
3
votes
0answers
83 views

Does composing the Frobenius with an automorphism give another Frobenius

Let $X_0$ be a variety over $\mathbf{F}_q$. Consider the Frobenius $F_0:X_0\to X_0$. Let $X= X_0\times \bar{\mathbf{F}_q}$ and let $F:X\to X$ be $F_0 \times \textrm{id}$. Let $f:X\to X$ be an ...
2
votes
0answers
21 views

How Do I Apply the Cantor-Zassenhaus algorithm to $\mathbb{F}_2$?

Recently, I've been trying to implement the Cantor-Zassenhaus algorithm in C++ over $\mathbb{F}_2$. According to this lecture, the algorithm is basically: Input is polynomial $f\in\mathbb{F}_q$ with ...
2
votes
0answers
23 views

Existence of a linear map in general position

Let $W$ and $T$ be linear spaces over $\mathbb F$, with $n=\dim(W)$ and $t=\dim(T)$. Let $U_1,\ldots,U_m$ be a family of subspaces of $W$ with $\dim(U_i)=r_i$ for each $i$. The linear map $\phi:W\to ...
2
votes
0answers
37 views

Show $ \mathbb{F}_2[x]/(x^3 + x^2 + 1) \simeq \mathbb{F}_2[t]/(t^3 + t + 1)$

$x^3 + x^2 + 1$ and $x^3 + x + 1$ are both irreducible over $\mathbb{F}_2[x]$, so then we have isomorphism of fields: $$ \mathbb{F}_2[x]/(x^3 + x^2 + 1) \simeq \mathbb{F}_2[t]/(t^3 + t + 1) \simeq ...