# Tagged Questions

The finite-fields tag has no usage guidance.

**2**

votes

**2**answers

174 views

### Cases of almost-linear time solvable linear systems

Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$
Solving for ${\bf x}$ through standard Gaussian Elimination ...

**0**

votes

**1**answer

220 views

### Low degree approximation of the polynomial extension of the logical-or function

Let $x\in\{0,1\}^n$ be a binary vector of dimension $n$, and let $OR(x)$ be the "logical or" function (i.e., returns $1$ if at least one of the coordinates is $1$ and otherwise returns $0$).
Consider ...

**0**

votes

**1**answer

202 views

### Finding an embedding efficiently in field extension of finite field

We know that $GF(p^c)$ is a subfield of $GF(p^{cn})$. Also we know that elements in $GF(p^c)$ can be represent by degree $c$ polynomials with coefficients in $\mathbb Z_p$, where multiplication is ...

**6**

votes

**1**answer

615 views

### Exponential sums over finite fields with even characteristic

I am looking for an elementary evaluation (if one exists) of the exponential sum
$$
G_r(a,b) = \sum_{x \in \mathbb{F}_{2^r}} \psi(ax^2 + bx),
$$
where $a,b \in \mathbb{F}_{2^r}^*$ are both units, ...

**1**

vote

**2**answers

281 views

### Minimum Growth Rate of Hamming Weight of Multiples of Primitive Polynomials

Let $F_2[x]$ denote the ring of polynomials over the field of 2 elements.
Richard Brent has a page on finding primitive trinomials in $F_2[x]$ of huge degree at ...

**8**

votes

**2**answers

479 views

### Invariant functor for admissible representations of reductive groups over local fields

Hello,
I have a question concerning a certain functor between represention categories. I'm rather sure this is already known, but I could not find a reference.
Let $F$ be a local non-archimedean ...

**4**

votes

**3**answers

649 views

### Field with cyclic product group

If a field has a cyclic multiplicative group, is it necessarily finite?

**5**

votes

**3**answers

879 views

### Fast Vandermonde matrix multiplication over finite field

Let $V_{i,j}=x_i^j$ where $x_i\in\mathbb F_q$ for $1\le i\le n,1\le j\le n$ be a Vandermonde matrix over finite field $\mathbb F_q$.
I wish to know the currently known fastest algorithms for ...

**1**

vote

**0**answers

319 views

### non-split Frobenius map

there are 3 simple groups arising from $SO(8)$, i.e.$ SO(8,F_{q})$, $2D_4(q,q^2)$,$3D_4(q,q^3),$
so I want to know
For the $3D_4(q,q^3),$, what is the corresponding Frobenius?

**1**

vote

**0**answers

240 views

### Sums of three squares in $GF(q)[t]$

Let $q$ be a power of an odd prime number $p>3,$ say $q=p^r$ with $r \geq 1.$
It is known that every polynomial $M$ in $GF(q)[t]$ is a sum of at most $3$ squares
with some conditions on degrees. ...

**3**

votes

**1**answer

272 views

### A kind of `pell` equation in characteristic $2.$

Given polynomials $a(t),b(t) \in K[t]$ where $K$ is a finite extension of $GF(2)$,
with
$$
a(t) \neq 0,
$$
we consider the equation
$$
x^2+axy+by^2=1
$$
with unknowns $x,y$ also polynomials in ...

**3**

votes

**2**answers

527 views

### Reducible trinomials $x^{odd}+x^2+s(t)$ in characteristic $2$

Let $F$ be a finite field of characteristic $2$. Let $m \geq 2 $ be a positive integer.
Seems unknown
if the trinomial
$$
T(t,x) = x^{2m+1}+x^2+s(t) \in F[t][x]
$$
(more explicitly, the ...

**6**

votes

**2**answers

402 views

### How do the number of plane curves over a finite field of a fixed genus increase with the degree?

Let $k$ be a finite field. We define $N(d,g)$ to be the number of plane curves $f(x,y)$ defined over $k$ of degree $d$ with (geometric) genus $g$. If $D(d) := (d-1)(d-2)/2$ (the maximum possible ...

**23**

votes

**1**answer

1k views

### How does Tate verify his own conjecture for the Fermat hypersurface?

This question is about Tate's 1963 paper "Algebraic Cycles and Poles of Zeta Functions". Here he announces a conjecture (now known as "the Tate conjecture") which states that certain classes in the ...

**1**

vote

**2**answers

694 views

### best deterministic complexity for factoring polynomials over finite field

I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, ...

**15**

votes

**2**answers

865 views

### Does $\mathbb{K}[G]\simeq\mathbb{K}[H]$ for some field $\mathbb{K}$ of characteristic $p$, imply $\mathbb{F}_p[G]\simeq\mathbb{F}_p[H]$?

Due to the first (and very helpful) answer I received, I've reformulated the question a little: $G$ and $H$ are now assumed to be $p$-groups.
Let $p$ be a prime, and let $\mathbb{F}_p$ be the field ...

**6**

votes

**7**answers

614 views

### Classifications of finite simple objects

I'm curious to know if other classifications are known of "finite simple structures" in the same spirit of the monumental classification of finite simple groups. Here I mean "classification" in the ...

**0**

votes

**1**answer

831 views

### nontrivial cube root of unity [closed]

Hi,
I have a finite field Fp with p = 11 mod(12) and I am trying to get the third nontrivial root of unity in Fp^2 = Fp^2[x]/(x^2+1). So, i need x where x^3=1.
Somehow I came into a source saying ...

**0**

votes

**1**answer

700 views

### Elliptic curve over finite field: scalar multiplication

I'm implementing arithmetics for elliptic curves over secp256r1 as a homework assignment.
For scalar multiplication, the assignment specifically specifies that $k$ is "any hexidecimal encoded ...

**3**

votes

**1**answer

3k views

### Number of n-th roots of unity over finite fields [closed]

How many $n$-th roots of unity does a finite field $\mathbb{GF}\left(p^k\right)$ have? ($p$ is prime). And then kind of related to that, is there a finite field with exactly $n_1,\ldots,n_N$ ...

**4**

votes

**1**answer

1k views

### Irreducibility of some trinomials modulo $p$

Let $n>1$ be an integer. An old result of Selmer,
See Theorem 1, page 289 in
http://www.mscand.dk/article.php?id=1472,
(If the link does not work try googling: ...

**1**

vote

**0**answers

182 views

### Binary `neighbors` perfect polynomials, instead of `consecutive`

Inspired by Andrei's nice solution of 52609, (namely consecutive perfect polynomials):
Denote by $A$ the full ring of polynomials in one variable $t$ over the ...

**3**

votes

**1**answer

270 views

### Can two Consecutive Polynomials both be perfect ?

Denote by $A$ the full ring of polynomials in one variable $t$ over the finite field with $q$ elements.
For any monic polynomial $P \in A$ define
$$
\sigma(P) = \sum_{d \mid P, d\, \text{monic}} d.
...

**1**

vote

**0**answers

333 views

### J. T. B. Beard's algorithm to catch `perfect polynomials`

For any monic polynomial $P$ with coefficients in a finite field of order $q$, we put
$$
\sigma(P) = \sum_{d \mid P, d \text{ monic}} d.
$$
Observe that $P$ and $\sigma(P)$ have the same degree.
...

**9**

votes

**1**answer

938 views

### All polynomials over a finite field are sums of $2$ square-free polynomials

I quote Proposition 2.3, page 14 lines -3 and -4 of Michael Rosen's book
Number Theory in Function Fields:
Let $b_n$ be the number of square-free monics in $A= \mathbb{F}_q[t]$ of degree $n.$
Then ...

**2**

votes

**1**answer

235 views

### Quadratic forms without common zeroes

A question which, I suppose, is as easy as abc for an expert. For a given finite field $F$ of odd characteristic (if needed, the characteristic is $3$ and the size of $F$ is large), do there exist two ...

**0**

votes

**0**answers

133 views

### elementary question on ECDLP

If $\mathbb{F}_q$ is a finite field and the elliptic curve E is defined over finite field $\mathbb{F}_p$ such that ECDLP is hard in E($\mathbb{F}_p$), where $q, p$ are prime and $q \ll p$. Let T $\in ...

**3**

votes

**0**answers

333 views

### Finch's sequence over $\mathbb{F}_3$

In http://algo.inria.fr/csolve/seqmod3.pdf -- "Periodicity in sequences mod 3" Steven Finch (also cited in Sloane's OEIS A112683) defines the following sequences in $\mathbb{F}_3$:
For each positive ...

**23**

votes

**2**answers

1k views

### Does the etale fundamental group of the projective line minus a finite number of points over a finite field depend on the points?

Clearly the etale fundamental group of $\mathbb{P}^1_{\mathbb{C}} \setminus \{a_1,...,a_r\}$ doesn't depend on the $a_i$'s, because it is the profinite completion of the topological fundamental group. ...

**3**

votes

**1**answer

1k views

### Finite fields: Is multiplicative order of $x^p - x - 1$ equal to $\frac{p^p-1}{p-1}$ over GF(p)? [duplicate]

Possible Duplicate:
Multiplicative order of zeros of the Artin-Schreier Polynomial
I will be grateful for any reference to some literature on the following question (to the best of my ...

**13**

votes

**0**answers

493 views

### Noether-Deuring for injections and surjections?

Noether-Deuring theorem (not in the strongest form, but in the one I usually need):
Let $L\diagup K$ be a field extension. Let $A$ be a $K$-algebra which is finite-dimensional as a vector space over ...

**10**

votes

**2**answers

783 views

### Multiplicative order of zeros of the Artin-Schreier Polynomial

This question was asked on NMBRTHRY by Kurt Foster:
If $p$ is a prime number and $\mathbb{F}_p$ the field of $p$ elements, the zeroes of the Artin-Schreier polynomial
$x^p - x - 1 \in ...

**4**

votes

**1**answer

496 views

### A silly question: is the number of points on a Jacobian (of a curve, over a finite field) known?

In a cryptography book I read that people does not known how to compute the number of points on a Jacobian of a hyperelliptic curve $C$ over a finite field $F_q$? Is this true? It seems easy to ...

**7**

votes

**2**answers

509 views

### Gelfand-Tsetlin bases for Lie groups over finite fields

There is a method of constructing representations of classical Lie algebras via Gelfand-Tsetlin bases. It has also been applied to Symmetric groups by Vershik and Okounkov. Does anybody know of any ...

**12**

votes

**1**answer

727 views

### A family of hypersurfaces with many points

This question is a sequel to an earlier question, which asked about the zeta function of a certain affine variety over a finite field $k$. The unusual thing about this variety is that it had the ...

**4**

votes

**0**answers

348 views

### Given two linear operators A and B over a finite field, is there a third operator C whose kernel is the intersection of kernels of A and B?

Let $V$ be a finite dimensional linear space over a finite field $k$. Let $A$ and $B$ be two endomorphisms of $V$.
Question 1. Is there an endomorphism $C$ of $V$, which is expressed in terms of ...

**47**

votes

**6**answers

4k views

### How to recognise that the polynomial method might work

A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let ...

**2**

votes

**2**answers

489 views

### Polynomials over Z evaluated with finite field arguments

A) Given a non-constant polynomial $q\in\mathbb{Z}[\alpha_1,\alpha_2,\ldots,\alpha_n],$ if we pick random $\omega_i\in\mathbb{F}$ (a finite field) uniformly and independently across $1\leq i\leq n,$ ...

**2**

votes

**2**answers

315 views

### vectors with entries from a finite ring

I've been working recently with vectors over finite fields, but I was hoping to work in a more general setting and consider vectors over finite commutative rings. The question I had is as follows: if ...

**2**

votes

**1**answer

509 views

### Existence question on rational points on a curve

I am puzzled about the following question:
Let C be a smooth, projective, absolutely irreducible curve defined over GF(q) and let g denote the genus of C. O is a rational point on C, and the divisor ...

**8**

votes

**1**answer

527 views

### Number of irreducible polynomials with some coefficients fixed over a finite field

I am interested in the following problem: I have a finite field $F_q$, two positive integers
$n>m$ and elements $a_1,...,a_m\in F_q$. How many of the polynomials
...

**1**

vote

**1**answer

533 views

### maximal number of mutually orthogonal vectors

Let $F$ be a field, $n$ be a positive integer. Denote by $h_{F}(n)$ the maximal dimension of a subspace $X\subset F^n$ such that $(x,y)=0$ for any two (not necessary distinct) vectors $x,y\in F^n$, ...

**3**

votes

**3**answers

629 views

### how to generate the n-torsion group

Hello,
I was curious about the following sentence: "then the $n$-torsion on $E(\overline{K})$ has known structure, as a Cartesian product of two cyclic groups of order $n$" (found at ...

**8**

votes

**0**answers

994 views

### roots of quadratic forms

This may be a very silly question, but I was wondering what is known about the roots of a quadratic form over variables $x_1,\ldots,x_n,y_1,\ldots,y_m$ in the finite field $\mathbb{F}_p$. I'm not ...

**8**

votes

**1**answer

2k views

### Order of finite unitary group

This may be an easy exercise but I am not getting it. Let $\mathbf F_q$ be a finite field with $q$ elements and $\mathbf F_{q^2}$ be its degree two extension. Define an automorphism $\sigma$ of ...

**1**

vote

**1**answer

504 views

### Number of subset sums

Let $\mathbb{F}_q$ be a finite field with characteristic $p$ and $p < q$ (i.e. not a prime field). Let $D\subseteq \mathbb{F}_q$ be a some set with $|D|=n$. Find a non-empty subset ...

**4**

votes

**1**answer

524 views

### Elements of trace zero in a field extension

Let $K=F_q$ and $F=F_{q^3}$, define the set A={$x \in F$ : $Tr_{F/K} (x)=0$}.
Is it true that for every $x \in A$ there are $y,z \in A$ such that $x=yz$?

**2**

votes

**2**answers

485 views

### Elliptic curves over proper variety over $\mathbf{F}_q$ isotrivial

Why is every elliptic curve over a proper (edit: smooth and geometrically connected) base over $\mathbf{F}_q$ isotrivial, i.e. is constant after base changing with $\bar{\mathbf{F}}_q$? If the moduli ...

**1**

vote

**1**answer

165 views

### Sub-representations of the affine group

Let $F=\mathrm{GF}\left(p^k\right)$ be any finite field. Let $G$ be the group of all affine permutations on $F$ (i.e. permutations of form $x\mapsto ax+b$). Then the set of all functions from $F$ to ...

**19**

votes

**4**answers

1k views

### Non-split extensions of $GL_n(F_q)$ by $F_q^n$ ?

A very naive question :
I just learned that there is a non-split extension of $GL_3(F_2)$ by $F_2^3$ (with standard action). It can be realized as the subgroup of the automorphism group $G_2$ of ...