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

13
votes
0answers
136 views

What is the connection between Weil's character bound and Riemann Hypothesis over finite fields

Weil's character bound states that: Let $\mathbb{F}_{q}$ be a finite field of size $q$. Let $\chi$ be a multiplicative character of order $m$. Let $f(x)$ be a polynomial of degree $d$ such that $f(x) ...
11
votes
0answers
144 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 ...
9
votes
0answers
125 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
426 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
109 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
131 views

Existence of a special set of q+2 points in the finite affine plane over $\mathbb F_q$

I am working in the finite affine plane over $\mathbb F_q$ with $q=2^n$. Such a plane has $q^2$ points, $q^2+q$ lines, each line has $q$ points, and by a point is passing $q+1$ lines. There are $q+1$ ...
5
votes
0answers
120 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
70 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 ...
4
votes
0answers
99 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
103 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
50 views

Calculations in the field $\mathbb{F}_{13}$

The text i am reading claims that $\frac{246}{14}=1$ in the field $\mathbb{F}_{13}$. However, i cannot figure out why this is correct. Since $13 \cdot 18 = 234 \Rightarrow 246 = 12$ and $14 = 1$. How ...
4
votes
0answers
378 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
124 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
90 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
28 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
50 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
30 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
62 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
56 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
128 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
474 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
85 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
131 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
72 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
50 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 ...
2
votes
0answers
24 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 ...
2
votes
0answers
11 views

Subspace-evasive set performance in the random case

A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough ...
2
votes
0answers
41 views

Roots of polynomial in $F_3[x]$

Let $\alpha$ be a root of $x^2 + x + 2 = 0$ in $F_3[x]$. I am asked to show that $x^3 + x + 1$ has roots $\alpha$, $\alpha^2$ and $\alpha^4$. I started by observing that $\alpha^2 + \alpha + 2 = 0 ...
2
votes
0answers
44 views

Uniqueness of projective plane of order 5

Is there a slick way to see the uniqueness of projective plane (equivalently, an affine plane) of order $5$?
2
votes
0answers
60 views

Factor polynomials into irreducibles over GF(q)

The polynomials $x^4+x^3+1$ and $x^4+x^3+x^2+x+1$ are irreducibles over GF(2). (a) Factor both polynomials into irreducibles over GF(4). (b) Factor both polynomials into irreducibles over GF(8). I ...
2
votes
0answers
54 views

What's the connection between irreducible polynomials and fixed-frobenius elements in a finite ring?

Consider the ring $A_{p,n} = \mathbb{F}_p [x]/ (x^{p^n}-x)$. It has a basis $\{1, x, x^2, \ldots, x^{p^n - 1}\}$. The Frobenius endomorphism $x \mapsto x^p$ permutes elements of this basis. I've ...
2
votes
0answers
72 views

Multiplication in $\text{GF}(2^n)$

Computing products in $\text{GF}(2^n)$ involves choosing a prime modulus polynomial to "reduce" by. In the case that there are several such polynomials to choose from, do they all yield identical ...
2
votes
0answers
181 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 ...
2
votes
0answers
82 views

Number of solutions of $x^m \neq y^m$, $z^n=w^n=t^n$ over a finite field.

I am trying to compute the number of solutions of the following system of equations over a finite field $\mathbb{F}_q$ ($q$ may be considered odd prime power or just odd prime if needed): $$ x^m \neq ...
2
votes
0answers
79 views

Proof for the distributivity of multiplication over addition for a Binary Field

For the standard binary field $\mathbb{F}_{2} = \{0, 1\}$. Where the operations of addition and multiplication exist, and multiplication is equivalent to logical and, and addition is equivalent to ...
2
votes
0answers
109 views

Modular Inverse over some given finite field. Which method is more efficient?

I'm trying to do division in some given finite field (let's say mod p). I have 2 Python methods here that are currently doing that, but I'm not sure which is better or if 1 or both is simply wrong. ...
2
votes
0answers
100 views

Should I learn Commutative rings or finite fields “first” when self teaching?

My goal is to fully understand this answer on crypto.stackexchange by self-teaching myself all the basics. The term I'm working on now is a "Galois field", and starting on this wiki page. The header ...
2
votes
0answers
50 views

counting symmetric nilpotent matrices

In a recent paper [ Counting symmetric nilpotent matrices , by A. Brouwer], the author states that the number of 3x3 symmetric nilpotent matrices over the field of q elements is given by the ...
2
votes
0answers
200 views

Irreducible polynomial roots and representations for Galois field elements in normal basis

I am trying to understand some topics in the literature and came across the following problem. Say I have a field $GF(2^4)$ defined by the irreducible polynomial $r(z) = z^4 + z + 1$, and I want to ...
2
votes
0answers
85 views

Full Rank Matrix with a specific construction

Assume that we have a $p \times p$ matrix $Z$ over $\mathbb{F}_{2^p}$ $$Z=\begin{bmatrix} w_1 & w_1^2& w_1^4& ... & {w_1}^{2^{\frac{p}{2}-1}} & \alpha_1w_1 & ...
2
votes
0answers
48 views

Different elliptic curves over given $\mathbb{F}_q$ can have different orders?

As the title says: For a given $q \in \mathbb{N}$, in $\mathbb{F}_q$, is it true that different curves on it can have different group orders? I assume yes. Let $q:=5$. Wikipedia gives $9$ points for ...
2
votes
0answers
94 views

What's the fastest way to solve these equations with powers in a field?

This is for an algorithm I'm working on. Perhaps we can work together! We can consider the integers modulo a prime $p$. They form a field with arithmetic operations modulo $p$. I'd like to find ...
1
vote
0answers
38 views

Root of polynomial and field extension

I would be really thankful for any input. I am facing following problem. Given extension of finite fields $L/K$ of degree $3$, prove that every polynomial of degree $3$ with coefficients in $K$ does ...
1
vote
0answers
32 views

Rational equality modulo $p$

Assume that we have two rational expressions $f,g\in \mathbb{Z}(x,y_1,\ldots,y_n)$ with the property that the variable $x$ can only appear in the numerator of $f$ while only in the denominator of $g$. ...
1
vote
0answers
17 views

How to show that the normalizer N of a Sylow $p$-subgroup P of $S_p$ in $S_p$ is the affine linear group AGL(1,$p$)?

I want to prove this as a special case of another fact that the normalizer of G in the group of set-bijections of G is isomorphic to the semi-direct product of Aut(G) and G itself. How do I link up ...
1
vote
0answers
13 views

Is a Spread Unique?

Let $V$ be a vector space of dimension $n$. It is well known that when $r | n$, there is a set of disjoint $r$-dimensional subspaces of $V$, which covers $V$, called Spread. My question is that is a ...
1
vote
0answers
21 views

Computation of the 2-torsion group of an elliptic curve

I have some troubles solving the following problem: Let $E$ be the elliptic curve $E:y^2+2y=x^3+x+9$ over $\mathbb{F}_{16}$. Compute the 2-torsion group $E[2]$, i.e. find all the points of order $2$ ...
1
vote
0answers
36 views

Showing the existence of sub fields of a finite field

For each divisor $m$ of $n$, $GF(p^n)$ has a unique sub field of order $p^m$ . The proof of this theorem in Gallian goes like this : Suppose that $m$ divides $n$. Then, since : $(p^n-1) = ...
1
vote
0answers
40 views

Galois Group of $x^p-x+a$ over $\mathbb{F}_p$ for prime $p$ and $a\neq 0\in \mathbb{F}_p$

Question is to find Galois group of $f(x)=x^p-x+a$ over $\mathbb{F}_p$ for prime $p$ and $a\neq 0\in \mathbb{F}_p$ What i have done so far is : I could see that $f(x)$ is Irreducible and ...
1
vote
0answers
62 views

GCD of high order polynomials(modulo large prime)

I want to solve the following question: Consider a polynomial $f(x)=a_0+a_1*x^{e_1}+a_2*x^{e_2}+\cdots+x^{e_m}\in F_p[x]$ where $p$ is a prime such that $\log(p)\sim m$ and $e_m\sim 2^m$, I want to ...