Skip to main content

Questions tagged [finite-fields]

A finite field is a field with a finite number of elements. For each prime power $q^k$, there is a unique (up to isomorphism) finite field with $q^k$ elements. Up to isomorphism, these are the only finite fields.

Filter by
Sorted by
Tagged with
0 votes
0 answers
36 views

Is generating semirandom blake256 hashes until packed points is on the curve, a safe algorithm to avoid the discrete log between the generated points?

I know there are more robust methods, but I wanted to know about this specific one For any distinct said randomly generated point : $P_i,P_j\in \{P_1,...,P_k\}$ it should be hard to find $s$ such that ...
user2284570's user avatar
4 votes
1 answer
199 views

Bounds on quadratic character sums

I asked this question on Mathematics stack exchange but didn't get a response, so I ask here too. Let $\chi$ be the non-trivial quadratic character of $\mathbb{F}_q$, and let $f(x)$ be a square-free ...
Madarb's user avatar
  • 153
0 votes
0 answers
23 views

Solving sparse bilinear systems with a relatively large number of variables

I'm trying to solve a bilinear system of equations over a finite field. (More specifically: I'm trying to find a single solution, if one exists.) The system consists of equations of the form $$y^T A_i ...
Sic Vis's user avatar
  • 101
2 votes
1 answer
110 views

Asymptotic size of largest subset in $\mathbb F_p^2$ defining only lines of different slopes

Suppose that all lines defined by pairs of distinct elements in a subset of $\mathbb F_p^2$ have different slopes. How large can such a subset be asymptotically (for primes $p\rightarrow \infty$)? ...
Roland Bacher's user avatar
2 votes
1 answer
68 views

Under row operations and column permutations a matrix A can be put in the non-unique form ( I | X ), what is known about the set of possible X?

Given a full row-rank matrix $A$, this can be put into a unique reduced row echelon form via elementary row operations. Allow column permutations (no column addition / multiplication) and this can be ...
DeafIdiotGod's user avatar
0 votes
0 answers
94 views

Algebraic independence and substitution for quadratics

Let $f_{1},...,f_{n-1} \in \mathbb{F}[x_1,...,x_n]$ such that $\{ f_1,..., f_{n-1},x_n \}$ is algebraically independent over $\mathbb{F}$. Let $G \in \mathbb{F}[x_1,...,x_n,y_1,...,y_{n-1}]\...
Rishabh Kothary's user avatar
0 votes
0 answers
110 views

Relation between minimality and algebraic independence for binomials?

$\DeclareMathOperator\supp{supp}$Given $f_1,...,f_n \in \mathbb{F}[x_1,...,x_n]$ such that $f_1 = x_1 + q_1$ $f_2 = x_2 + q_2$ $\cdot \cdot \cdot$ $f_{n-1} = x_{n-1} + q_{n-1}$ $f_{n} = q_n$ such that ...
Rishabh Kothary's user avatar
2 votes
1 answer
194 views

Minimality implies algebraic independence?

$\DeclareMathOperator\supp{supp}$Given $f_1,...,f_n \in \mathbb{F}[x_1,...,x_n]$ such that $f_1 = x_1 + q_1$ $f_2 = x_2 + q_2$ $\cdot \cdot \cdot$ $f_{n-1} = x_{n-1} + q_{n-1}$ $f_{n} = q_n$ such that ...
Rishabh Kothary's user avatar
1 vote
0 answers
58 views

Are these kinds of bases for $\mathbb{F}_2^q$ seen as a vector space studied?

In the context of my research, I have to work with sets of vectors $\left\{y_i\right\}_{i\in[n+1]}$ of $\mathbb{F}_2^n$ such that the following property is true: $$\forall i\in[n+1], \left\{y_i\oplus ...
Tristan Nemoz's user avatar
0 votes
0 answers
37 views

Counting zero-sum subsets of a finite field with a particular form

Let $\mathbb{F}$ be a finite prime field of characteristic different than $2$ and $\beta \in \mathbb{F}$ a generator of the $2$-power order multiplicative subgroup of order $2^k$, so $\beta^{2^{k-1}} =...
dorebell's user avatar
  • 2,998
0 votes
0 answers
75 views

Bounding the dimension of $H^1(G, V\otimes V^{\vee})$

Let $G_S$ denote the Galois group of the maximal extension of $\mathbb{Q}$ unramified away from a finite set of primes, $S$. Let $V$ be a finite dimensional, $G_S$-representation over $\mathbb{F}_p$ (...
kindasorta's user avatar
  • 2,085
3 votes
1 answer
309 views

Sum of products of Fourier coefficients in finite field

Let $\mathbb{F_q}$ be some finite field and let $f,g: \mathbb{F_q} \to \mathbb{C}$. By $\hat{f}, \hat{g}$ let's denote the Fourier coefficients of $f,g$ with respect to the additive characters of the ...
User's user avatar
  • 153
6 votes
0 answers
151 views

Fundamental lemma of sieve theory in function fields

Is there any literature concerning the fundamental lemma of sieve theory in $\mathbb{F}_q[T]$? In integers there are various versions of the lemma (bases on different sieves); I would be happy with ...
Ofir Gorodetsky's user avatar
1 vote
1 answer
90 views

Expected number of solutions of a random quadratic polynomial system over a finite field

Let $\mathbb{F}_q$ be a field of $q$ elements. Let $a_{i,j,k}$, $b_{i,j}$, $c_i$ ($1 \leq i \leq m$, $1 \leq j \leq k \leq n$) be independent uniformly distributed random variables in $\mathbb{F}_q$, ...
en-drix's user avatar
  • 93
0 votes
0 answers
31 views

Endomorphism of torsion points of Drinfeld modules

Reposting from mathstackexchange. A Drinfeld module is defined to be an $\mathbb F_q$-algebra morphism $\phi: \mathbb F_q[T] \rightarrow K\{\tau\}$, where $K=\mathbb F_{q^m}$ is a finite field and $K\{...
Reyx_0's user avatar
  • 149
1 vote
0 answers
82 views

When does sum of algebraically independent polynomial become dependent?

Given $f_1,...,f_n \in \mathbb{F}[x_1,...,x_n]$ where $f_n = g + h$. Suppose the sets $\{ f_1,...,f_{n-1},g \}$ and $\{ f_1,...,f_{n-1},h \}$ are algebraically independent then is there a ...
Rishabh Kothary's user avatar
1 vote
0 answers
121 views

Solution formula in an explicit equation over $\mathbb{F}_p^3$

I'm looking into a formula involving prime numbers $p \geq 7$ and an equation's solutions. The equation in question is: $$z^2 = (x^2 - 4x)(y^2 - 4y)((x + 1 - y)^2 - 4x),$$ where $(x,y,z)\in \mathbb{F}...
Eric's user avatar
  • 71
0 votes
0 answers
94 views

Is there an inner product on $\mathbb{F}_p\left[S_n\right]$ for which $\langle x, x \rangle \ne 0$ for all $x$?

Let $\mathbb{F}_p\left[S_n\right]$ be the group algebra of the symmetric group $S_n$ over the finite field $\mathbb{F}_p$. One can define an "inner product" in the usual way: $$\langle x,y \...
Jackson Walters's user avatar
0 votes
0 answers
41 views

When does the sum of squares/cubes of polynomials over finite field have less than maximum degree?

Given polynomials $p_1(x), p_2(x), \dots p_m(x) \in \mathbb{F}_p[x]/\langle x^p-x\rangle$ where $p$ is a prime, when does $\sum_{i=1}^m p^2_i(x)$ have degree $< p-1$? What about $\sum_{i=1}^m p^3_i(...
Tanay Saha's user avatar
9 votes
0 answers
181 views

Who was the first to prove that the automorphism group of a finite field is cyclic and is generated by the Frobenius automorphism?

$\DeclareMathOperator\Aut{Aut}$It is well-known that the automorphism group $\Aut(F)$ of a finite field $F$ of characteristic $p$ is cyclic of order $n$ where $|F|=p^n$. Moreover, the cyclic group $\...
Taras Banakh's user avatar
  • 41.1k
5 votes
1 answer
169 views

Rational functions of order $3$

Let $p$ be a prime, let $\mathbb K$ a field with $\operatorname{char}(\mathbb K)=p$ and $\mathbb{K}(x)$ be the field of fractions of the polynomial ring $\mathbb{K}[x]$, i.e. $$\mathbb{K}(x)=\left\{\...
Mersn's user avatar
  • 51
0 votes
0 answers
175 views

Degree 6 Galois extension over $\mathbb{Q} $

Let L be the splitting field of $ x^3- 2$ over $ \mathbb{Q}$. Then $ G=\operatorname{Gal}(L/K) \cong S_3$. Let $\sigma\in G$ such that the fixed field of $ \sigma$ is $\mathbb{Q}(2^{1/3})$. Let $x,y\...
Sky's user avatar
  • 913
0 votes
0 answers
76 views

Number of solutions $x$ of equation $a_1 b_1^x + \dotsb + a_n b_n^x=0$ over a finite field

Let $F$ be a finite field and let $a_1, b_1, \dotsc, a_n, b_n \in F$ be field elements. I am interested in the number of solutions $0\leq x \leq |F|-1$ such that \begin{equation}\label{e:1} a_1 b_1^x +...
Albert Garreta's user avatar
10 votes
2 answers
496 views

Isomorphic finite fields of a skew field

Let $D$ be a skew field and $F$ and $E$ be isomorphic finite subfields of $D$, is it true that $F=E$?
Alborz Azarang's user avatar
1 vote
1 answer
173 views

Matrices over a finite field: matrices for which some unipotent $U$ satisfies Trace$(ZU)=0$ for all $Z$ in the commutant

Let $p$ be an odd prime number, let $A\in M_p(\mathbb{F}_p)$ be a $p$-by-$p$ matrix with coefficients in $\mathbb{F}_p$, let $C(A)$ be the commutant of $A$, and let $N\in M_p(\mathbb{F}_p)$ be a ...
loup blanc's user avatar
  • 3,594
0 votes
1 answer
112 views

Loss of degree for polynomials

Let $q$ be a power of a prime $p$, $m$ be an integer greater than $0$. Does there exist polynomials $P_0,\cdots,P_m$ of $\mathbb F_q[T]$ not all in $\mathbb F_q$ such that there exist polynomials $Q_0,...
joaopa's user avatar
  • 3,801
0 votes
1 answer
185 views

Constructing a family of $3$-wise independence functions from $\mathbb{Z}_p^n \rightarrow \mathbb{Z}_p$

A family of function hash functions $\mathcal{H}:\{h:N\rightarrow M\}$ is call $k$-wise independent if whenenver $h$ is drawn uniformly from $\mathcal{H}$, let $x_1,\ldots,x_k$ be distinct elements of ...
some1fromhell's user avatar
3 votes
0 answers
168 views

Characters of finite fields - Reference request

Let $\mathbf{F}_q$ ($q=p^f$) be a finite field. We are interested in the characters $\chi: \mathbf{F}_q\rightarrow \mathbf{K}$ ($\chi(0)=0$) where the $ \mathbf{K}$ is an alg.closed field of ...
Grad Student's user avatar
8 votes
1 answer
611 views

A question on algebraic independence

Let $f_1,f_2,\ldots,f_n, g \in \mathbb{F}_q[x_1,...,x_m]$. Assume that $f_1,\ldots,f_n$ vanish at $0$, so that $\mathbb{F}_q[[f_1,...,f_n]]$ is a subring of $\mathbb{F}_q[[x_1,...,x_n]]$. Suppose that ...
Rishabh Kothary's user avatar
4 votes
0 answers
159 views

When is $q$ invertible mod $m$, mod its order mod $m$, mod its order mod its order mod $m$, ad infinitum?

Fix an [edit: positive] integer $q$. Let me say that an [edit: positive] integer $m$ is IK over $q$ if $q$ and $m$ are coprime and the (multiplicative) order of $q$ mod $m$ is IK over $q$. Note that ...
Theo Johnson-Freyd's user avatar
0 votes
0 answers
116 views

A question on a system of quadratic polynomials

Consider the following system of quadratic polynomials $f_1,...,f_n \in \bar{\mathbb{F}}_2[x_1,....,x_n]$ : $f_1 (\bar{x}) = x_1 + x_n^2 + q_1$ $f_i(\bar{x}) = x_i + q_i$ for $i \in \{2,...,n-1 \}$ $...
Rishabh Kothary's user avatar
2 votes
1 answer
138 views

Are there a few input bits that randomize the output of an $\mathbb{F}_2$ polynomial?

Suppose $f:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$ is a degree $d$ polynomial and $\epsilon>0$ is some real number. Does there necessarily exist a set $C\subset [n]$ of coordinates with the size of ...
dankane's user avatar
  • 21
3 votes
0 answers
103 views

A question on the averages of Kloosterman sums

Sorry to disturb. Recently, I encountered a puzzle on the sums involving two Kloosterman sums. That is, For any $h, q_1,q_2\in \mathbb{N}$ with $(q_1,q_2)=1$ and $Q>1$, how two get a bound $$\sum_{...
hofnumber's user avatar
  • 553
2 votes
0 answers
121 views

Can K$_3$ of finite fields be related to Teichmüller cocycles?

This is sort of a blind shot, but... For a ring $R$, its third algebraic K-group is given by $\operatorname K_3(R)=H_3(\operatorname{St}(R))$. To simplify matters, let $R$ be a finite field $\mathbb ...
მამუკა ჯიბლაძე's user avatar
4 votes
1 answer
239 views

Frobenius and regular scheme

Let $X$ be a noetherian regular scheme over $\mathbb{F}_{p}$. Then by Kunz's theorem, the absolute Frobenius $F: X\rightarrow X$ is flat and integral. Can it be written as a projective limit of finite ...
prochet's user avatar
  • 3,442
2 votes
2 answers
427 views

Defining a sign of square roots in GF(p)

$\DeclareMathOperator\GF{GF}$Consider the following expression: $$ \sqrt{a_1} \pm \sqrt{a_2} \pm \dots \pm \sqrt{a_n} = 0, $$ where $a_1, \dots, a_n$ are positive integers. We want to find the number ...
Oleksandr  Kulkov's user avatar
0 votes
0 answers
109 views

Characterisation of even characteristic quadratic system

$\DeclareMathOperator\supp{supp}$Let $f_i \in \bar{\mathbb{F}}_2[x_1,..,x_5]$ for $1 \leq i \leq 5$ be such that $f_1(\bar{x}) = x_1 + x_5^2 + q_1$, $f_2(\bar{x}) = x_2 + x_1^2 + q_2$, $f_3(\bar{x}) = ...
Rishabh Kothary's user avatar
1 vote
1 answer
111 views

A question on classification of quadratic polynomials in even characteristic

$\DeclareMathOperator\supp{supp}$Let $f_1,...,f_n \in \bar{\mathbb{F}}_2[x_1,...,x_n]$ such that $f_i = x_i + q_i$ for $1\leq i \leq n-1$ and $f_n = q_n$ where $q_1,...,q_n$ are homogenous quadratic ...
Rishabh Kothary's user avatar
2 votes
2 answers
310 views

A graphic representation of classical unitals on 28 points

I would like to understand the geometry of the classical unitals. They are block designs containing $q^3+1$ points and whose blocks have cardinality $q+1$, where $q$ is a prime power. For $q=2$ (if I ...
Taras Banakh's user avatar
  • 41.1k
1 vote
1 answer
97 views

Existence of a symmetric matrix satisfying certain irreducible conditions

Let $K$ be a field such that $ \mathrm{char}(K) \neq 2 $. Let $ p(x) $ be an arbitrary irreducible polynomial over $K$ of degree $n$. Using the rational canonical form, we can always construct an $ n ...
Sky's user avatar
  • 913
1 vote
0 answers
68 views

Bias of $a^k / q$ modulo $q$?

Let $q$ be a prime. Let $0< a < q$ be an integer so that it is primitive modulo $q$. Let $k$ be a random integer up to $q-1$. Consider $$a^k = b_k + q * c_k$$ as $k$ varies modulo $q^2$. So $b_k$...
mtheorylord's user avatar
0 votes
1 answer
186 views

Trying to solve for the remainder of $a^q$ modulo $q$

Let $q$ be a prime and $a$ be a number from $0$ to $q-1$ (not an equivalence class). The elements $a^q$ are exactly the elements of order $q-1$ modulo $q^2$. I'm trying to solve the equation: $$a+2*\...
mtheorylord's user avatar
1 vote
1 answer
174 views

Algebraic independence of polynomials when truncated imply algebraic independence of the entire polynomial?

Let $f_1,\ldots,f_m \in \mathbb{F}[x_1,\ldots,x_n]$ and suppose $\hat{f}_i = f_i$ $\bmod \langle x_1,\ldots,x_n\rangle^3$ (i.e. the linear and quadratic part of $f_i$). Then if $\hat{f}_1,\ldots,\hat{...
Rishabh Kothary's user avatar
4 votes
0 answers
173 views

Intrinsic maps between complex integers modulo $p$ and integers modulo $p+2$

$\DeclareMathOperator\GF{GF}$Let $p$ and $p+2$ be twin primes. Let's assume that $-1$ is not a quadratic residue modulo $p$ (and therefore is a Q.R. modulo $p+2$). Consider the complex numbers $a+bi$ ...
mtheorylord's user avatar
2 votes
0 answers
69 views

Is the discrete logarithm equivalent to solving polynomial discrete logarithms?

Suppose we can quickly solve the discrete logarithm modulo $p$. Let's say $2$ is a generator so we can quickly find $l$ for which $2^l =h$ for any given target $h$. An interesting observation is that ...
mtheorylord's user avatar
1 vote
1 answer
224 views

On the estimate for a double exponential sum

I encounter a hyper-Kloosterman sum which needs some help from the experts here: For any integers $q,s \in \mathbb{N}^+$(which may not be necessarily co-prime with each other), how to bound the sum: $$...
hofnumber's user avatar
  • 553
0 votes
0 answers
90 views

A question on the evaluations of certain three-dimensional hyper-Kloostermans

There is a basic question regrading the 3-dimensional hyper-Kloosterman sum which needs some help from the experts here: For any integers $q,h \in \mathbb{N}$, how to estimate the sum: $$\sideset{_{}^{...
hofnumber's user avatar
  • 553
1 vote
0 answers
87 views

Functions that take quadratic residues to non quadratic residues

Let $p$ be prime and $Q$ be the set of integers $x$ mod $p$ so that $x^2-1$ is a quadratic residue. Let $Q^c$ be the complement of $Q$. If we don't consider $x = 1$ then these two sets have the same ...
mtheorylord's user avatar
4 votes
0 answers
258 views

Cosine Modulo $p$?

Consider the integers modulo a prime $p$. I'm looking for a nice polynomial function that acts as a sort of "cosine" on the integers modulo $p$. Specifically, I'm looking for solutions to ...
mtheorylord's user avatar
4 votes
1 answer
330 views

GCD in $\mathbb{F}_3[T]$ with powers of linear polynomials

This is a continuation of my previous question on $\gcd$s of polynomials of type $f^n - f$. Let us call $n > 1$ simple at a prime $p$ when $p-1 \mid n-1$ but $p^k - 1 \not\mid n-1$ for all $k > ...
Martin Brandenburg's user avatar

1
2 3 4 5
16