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)

11
votes
0answers
189 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 ...
10
votes
0answers
149 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 ...
10
votes
0answers
166 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 ...
6
votes
0answers
481 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
25 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
98 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 ...
5
votes
0answers
115 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
132 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
47 views

Existence of Jordan decomposition over finite field

Prove that over finite field $\mathbb F$ exists additive Jordan-Chevalley decomposition: for all matrix $M$ there are semisimple matrix $M_{s}$ and nilpotent matrix $M_{n}$ such that $M=M_{s}+M_{n}$. ...
4
votes
0answers
54 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
103 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
141 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
515 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
25 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
29 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
69 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
31 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
119 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
41 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
132 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
34 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
34 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
69 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
143 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 ...
3
votes
0answers
94 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
37 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
58 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
63 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
88 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
174 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
781 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
89 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
134 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
80 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
28 views

How to find the power of generator defined over finite field , $\mathbb F_{2 ^m}$?

List item Actually ,I am trying to execute the algorithm to find the power of generator of field(group) as shown in table of attached file but when k=7 and onward ,I could not understand what is ...
2
votes
0answers
53 views

Efficient computation of matrix determinant in finite ring

I am trying to implement generalization of Hill cipher. My idea is very simple: the size of key matrix should be arbitrary number not only three. All steps of this cipher is trivial except computation ...
2
votes
0answers
37 views

Subset of numbers analogous to primitive polynomials over finite fields

It is well known that many problems in number theory have an analogue on the ring of polynomials over finite fields and vice versa, the primes in $\mathbb{F}_q[x]$ being the irreducible polynomials. ...
2
votes
0answers
39 views

Shortened Reed-Solomon proving p(D) is primitive

Assume we have a shortened $(n=18, k=12, t=3)$ Reed Solomon code in $GF(2^{8})$.Let $\alpha$ be a primitive element of $GF(2^{8})$. Consider the primitive polynomial given by: $p(D) = D^{8} + D^{4} + ...
2
votes
0answers
56 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 ...
2
votes
0answers
34 views

Counting couples of square-free polynomials over finite fields

I have a curve defined by the following equations over the finite field $\mathbb{F}_q$ with $q=p^r$ with $p \geq 3$: $$C_{h_1,h_2}:\begin{cases} y_1^2=h_1(t) & \\ y_2^2=h_2(t) ...
2
votes
0answers
28 views

Showing that the fixed points of a homomorphism form a finite field.

I have the following question on my problem set. Suppose that $\textsf{k}$ is a field and $\phi:\textsf{k}\to\textsf{k}$ is a homomorphism. Check that $\textsf{k}^\phi=\{x\in\textsf{k}:\phi(x)=x\}$ ...
2
votes
0answers
38 views

When does a field of for which a set of matrices is defined on become important?

I have already gone through several linear algebra related courses without any notion of a field and I am having trouble reading a serious linear algebra book that talks about infinite field, so and ...
2
votes
0answers
46 views

Value of a Moebius sum

Let $q$ be a power of a prime, let $n \in \mathbb{N}$. Is the value of the following sum known? $$ \sum_{d \mid q^n-1} \mu\left( \dfrac{q^n-1}{d} \right) q^{ord_d(q)}, $$ where $ord_d(q)$ denotes ...
2
votes
0answers
60 views

Picking codewords that are close

Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and number of minimum weight codewords $N_d$. How many ways can you select codewords $c_1,\dots,c_T$ (assume $T\ll q^k$) such ...
2
votes
0answers
23 views

Conversion from/to power form and polynomial basis is a finite field

I'm trying to figure out if there is a way better than $O(m^2)$ of converting between the power form $(\alpha^n)$ to polynomial basis. Right now, I'm just enumerating the entire field up to the $n$-th ...
2
votes
0answers
37 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
2
votes
0answers
45 views

Generators of group of “unitary” matrices over a finite field

This is about a group related to $U(n,q)$ and $SU(n,q)$. I know from multiple sources the generators for these groups, but $U(n,q)$ is defined to be the group of matrices $A$ such that $A^*JA = J$ ...
2
votes
0answers
50 views

How can I predict what numbers “work” without brute force?

I've been doing some research with LFSRs and I have found something I can't explain. I've worked on it for years but I'm finally opening up to public involvement because I can't stand not knowing. ...
2
votes
0answers
100 views

How to prove that all primitive polynomials are irreducible

Let $F$ be a finite field, and $F[X]$ set of all polynomials in $F$, how to prove that: why all primitive polynomials $\;$ $f \in F[X]$ $\;$ must be an irreducible. Note: Polynomial primitive is an ...