# Tagged Questions

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)$.

383 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 ...
97 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) ...
199 views

179 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 ...
535 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 ...
137 views

90 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 ...
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 ...
188 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, ...
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 ...
71 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$ ...
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 ...
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 ...
51 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 ...
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 ...
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.
33 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 ...
69 views

735 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 ...
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 ...
769 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 ...
24 views

154 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 ...
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 ...
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$ ...
51 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....
45 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 ...
63 views

39 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) &...
324 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 ...
169 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 ...
157 views

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}$...
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.
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 ...