The tag has no wiki summary.

learn more… | top users | synonyms

-4
votes
0answers
32 views

finding points on elliptic curve over finite field [on hold]

Find the points on the elliptic curve y^2 = x^3 + 2x + 2 in F17 (field of prime 17). Do I have to guess a first point and then use an algorithm to spit out all other points?
6
votes
0answers
118 views

Algebraic dependency over $\mathbb{F}_{2}$

Let $f_{1},f_{2},\ldots,f_{n}$ be $n$ polynomials in $\mathbb{F}_{2}[x_{1},x_{2},\ldots,x_{n}]$ such that $\forall a=(a_1,a_2,\ldots,a_n)\in\mathbb{F}_{2}^{n}$ we have $\forall ...
0
votes
0answers
60 views

Eigenvalue of a linear map over finite field

Let $ F_q $ be a finite field with $ q $ elements. Let $ g $ be a multiplicative generator of $ F_{q^2}^* $. It implies that $ <g^{q+1}> = F_q^* $. Let $ l $ be a prime greater than $ q^2-1 ...
1
vote
1answer
225 views

When is an holomorphy ring a PID?

I posted this question on mathstackexchange but I realized it is probably more suitable for mathoverflow. I will use the notation and language of Stichtenoth, Algebraic Function Fields and Codes. ...
-2
votes
0answers
80 views

X^2e + X^e + 1 is irreducible for e which is a power of 3? [on hold]

I am looking for a proof or reference to the fact that the trinomials of the form X^2e + x^e + 1 Are irreducible in GF(2) for e which is a power of 3. Please help! Lear
-1
votes
0answers
125 views

elliptic curves and tower of finite fields [closed]

Let $E$ be an elliptic curve which is defined over $\mathbb{F}_{p^n}$ and $m< n$. Can we reduce $E(\mathbb{F}_{p^n})$ to $E(\mathbb{F}_{p^m})$? Specially in the case where $m=1$? I mean, let $A$ ...
6
votes
1answer
178 views

Distribution of the permanent modulo $p$

We know that the order of $SL_n({\mathbb F}_p)$ is $$p^{n(n-1)/2}(p^n-1)(p^{n-1}-1)\cdots(p^2-1).$$ Dividing by $p^{n^2}$, we deduce the probability that $\det$ takes the value $1$ over $M_n({\mathbb ...
6
votes
3answers
355 views

An infinite product associated with random matrices

Motivation Let ${\mathbb F}_q$ be the field with $q$ (a power of some prime number) elements. Then the order of $GL_n({\mathbb F}_q)$ is $$(q^n-1)(q^n-q)\cdots(q^n-q^{n-1}).$$ The fact that this ...
0
votes
1answer
100 views

Sylow-subgroups of the group of units of a finite field [closed]

Let $K$ be a finite field with $p^n$ elements. Then the group of unit is cyclic of order $p^n-1$. What are the primes which are dividing $p^n-1$? What are the Sylow-subgroups of the group of units of ...
10
votes
2answers
266 views

Is there a proof of Warning's Second Theorem using p-adic cohomology?

Let $\mathbb{F}_q$ be a finite field, $n \in \mathbb{Z}^+$, and $f_1,\ldots,f_r \in \mathbb{F}_q[t_1,\ldots,t_n]$ with $\operatorname{deg}(f_i) = d_i$. Put $d = \sum_{i=1}^n d_i$ and suppose $d< ...
16
votes
3answers
1k views

Classification of rings satisfying $a^4=a$

We have the famous classification of rings satisfying $a^2=a$ (for each element $a$) in terms of Stone spaces, via $X \mapsto C(X,\mathbb{F}_2)$. Similarly, rings satisfying $a^3=a$ are classified by ...
4
votes
0answers
135 views

Partial differential Equation over characteristic p

I want some references on partial differential equations over characteristic $p$. If we have a first order partial differential equation, how can we check whether there exists polynomials or rational ...
1
vote
0answers
77 views

Points on the intersection of an affine quadric and cubic over a finite field

Are there absolute constants $N$ and $B$ such that the following is true? Let $p>B$ be a prime. Let $q(x_0,\dotsc,x_n)$ and $c(x_0,\dotsc,x_n)$ be homogeneous of degree $2$ and $3$ with ...
4
votes
1answer
177 views

orthogonal group in characteristic 2

Let $O(2,\mathbb{Z}_2)$ be the orthogonal group of order two matrices. On $\mathbb{Z}_2$ there should exist just one odd quadratic form, hence the stabilizer subgroup $O^-$ of an odd quadratic for ...
6
votes
1answer
253 views

A parity counting problem for subsets over finite fields

Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$. For a subset $T\subseteq {\mathbb F}_p$, define $$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb ...
2
votes
0answers
86 views

Existence of roots of high order polynomial over finite fields

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 ...
2
votes
2answers
217 views

irreducible polynomials on the polynomial sequence

I suspect this problem is very famous and it must be studied very well. But I searched in Google and I did not find good reference. I will appreciate any answer and reference for any contribution ...
1
vote
0answers
43 views

Generate Finite Field power of g [closed]

consider the field F_2^4, defined by using polynomial representation with the irreducible polynomial f(x) = x^4 + x + 1. Given element g = (0010) as a generator for the field. How are the powers of g ...
5
votes
1answer
200 views

Over a finite field, does a torsor under the component group of G lift to a torsor under G?

Let $k$ be a finite field and $G$ a finite type smooth $k$-group scheme. Let $G^0$ and $\Gamma$ be the connected component of identity and the component group of $G$, so there is an exact sequence $1 ...
1
vote
1answer
113 views

Compressing a system of linear equations

Consider the system of linear equations $A\mathbf x=\mathbf b$ in which $A$ is an $m\times n$ matrix with $m < n$ and with the following property: Property $\Gamma$: Given $M=\{ M_1,\cdots,M_r ...
0
votes
0answers
80 views

Distinguish between odd and even powers of a in a finite field

In a finite field $\text{GF}(2^n)$ with characteristic 2, is there a relatively simple way to distinguish between the odd and even powers of the primitive element $a$? In other words, given an ...
0
votes
0answers
73 views

Eigenvalues of the Cayley-like graph

Let $ F_q $ be a finite field of characteristic 2. Let $ x^2 + Sx +P \in F_q[x] $ be an irreducible polynomial over $ F_q $, and let $ g $ be one of its roots in $ F_{q^2} $. Define a map $ M: ...
1
vote
0answers
87 views

In a finite field with characteristic 2, can I calculate the log(K+1) based on the log(K)?

In the equation $ a^x = a^y + 1$ over a finite field $\text{GF}(2^n)$, where '$a$' is the primitive element, can one calculate $x$ as a function of $y$ without having to resort to taking the logarithm ...
1
vote
0answers
229 views

Enumerating certain types of permutation polynomials

Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions: $f(ax) = af(x)$ for ...
0
votes
0answers
125 views

A matrix rank problem over finite fields: Is that a known problem?

I have already asked the same question on cstheory.SE, but I haven't got an acceptable answer. So, I decided to ask it here. It might be a known problem, however. Let $A \odot B$ denote elementwise ...
7
votes
0answers
186 views

A strong sum-product “for translates” in finite fields

In the course of some recent research, I've sketched out a proof of the following result. My basis question is: is the result interesting? Proposition There exists an absolute constant $c$ such ...
3
votes
2answers
330 views

Degrees of factors of polynomial $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$

I’m facing the problem of factoring polynomials of type $f(x)=x^q-(ax^2+bx+c)\in \mathbb{F}_q[x]$ and the degrees of factors seem to be quite special. For example, according to my experimental results ...
1
vote
1answer
187 views

Maximal separable extension of $\mathbb F_q((t))$

Let $K=\mathbb F_q((t))$. I want to prove that $K^{sep}$ is composite of $K^{sep}(p)$ and $K^{sep}(not \ p)$, where $K^{sep}(p)$ is maximal Galois extension of $K$ of exponent $p$, $K^{sep}(not \ p)$ ...
10
votes
5answers
807 views

Is $x^p-x+1$ always irreducible in $F_p[x]$?

It seems that for any prime number $p$ and for any non-zero element $a$ in the finite field $\mathbb F_p$, the polynomial $x^p-x+a$ is irreducible over $\mathbb F_p$. (It is of course obvious that ...
0
votes
0answers
92 views

Has this type of Cayley graphs been studied before?

Let $\mathbb F_q $ be a finite field of characteristic 2. Let $ x^2 + Sx +P \in \mathbb F_q[x] $ be an irreducible polynomial over $ \mathbb F_q $. Let $$ T = \{ \left( \begin{matrix} ...
9
votes
1answer
292 views

Motives over finite field not generated by hyperelliptic curves

So the question is that, over a finite field, does there exist an abelian variety $A$ for which there does not exist a generically one-to-one morphism from a hyperelliptic curve $C$ to $A$. p.s. A ...
1
vote
0answers
60 views

How can I decode efficiently a triple-error-correcting binary BCH code?

In a given $\mathrm{BCH}(N,K)$, $T=3$ code over $\mathrm{GF}(2^m)$, there are ways to find the error locations in a given N-bit codeword directly from the syndromes without going through the normal ...
5
votes
1answer
410 views

How can I solve a cubic equation in a finite field with characteristic 2?

I need to solve the usual cubic equation $x^3 + ax^2 + bx + c = 0$ over a finite field $GF(2^n)$. This is to avoid doing a brute-force Chien search in a BCH decoder. I read in a paper about an easy ...
3
votes
1answer
107 views

Higher Discrete logarithms over finite fields

The polylogarithm function is defined by $$Li_s(z)=\sum_{k=1}^\infty\frac{z^k}{k^s}.$$ At $s=1$, we have the natural logarithm function. We have the inverse of natural logarithm function as the ...
4
votes
0answers
160 views

# roots of polynomials over GF(2)

Consider a polynomial $p(x)$ with of degree $d$ with coefficients in $GF(2)$. How many roots can it have in $GF(2^m)$? The intent here is that $d \ll 2^m$. The trivial bound is of course $\leq d$. ...
2
votes
1answer
74 views

Stabilizer of a nonsingular vector in a quadratic space (char (k)=2)

suppose that $k$ is a finite field of characteristic 2 and $(V,q)$ a quadratic space, i.e., $V$ is a $k$-vector space and $q:V\to k$ quadratic form. Suppose that $\dim(V)\geq 4$ and that $q$ is ...
2
votes
0answers
71 views

Intersection of two trace equations over finite fields

Let $F_q$ be a finite field with $q$ elements. Let $n$ be an integer and $Tr:F_{q^n} \rightarrow F_q$ the trace function. My question is: For which integer $k$, $$\{x: Tr(x)=0\}\cap\{x: ...
35
votes
2answers
848 views

A curious identity related to finite fields

To three elements $a_1$, $a_2$, $a_3$ in the finite field $\mathbb F_q$ of $q$ elements we associate the number $N(a_1,a_2,a_3)$ of elements $a_0\in \mathbb F_q$ such that the polynomial ...
0
votes
1answer
314 views

Generators of cyclic group of finite fields

Let $F$ be a finite field and $f(x)\in F[X]$ be an irreducible polynomial of degree $n$. Let $\alpha$ be a root of $f(x)$. So $E:=F[\alpha]$ is a finite field of order $|F|^{n}$. We know that ...
4
votes
1answer
160 views

Constructing GF(2^n) in poly(n) time

I need to, on input $n$, deterministically, in poly(n) time, construct $GF(2^n)$. There is a very simple randomized algorithm (pick a random polynomial, check if it's irreducible; if not, repeat). ...
4
votes
2answers
324 views

When are arithmetic and geometric monodromy equal?

Let $f: Y\to X$ be a finite separable morphism of curves over the finite field $\mathbb{F}_q$. Is there a simple condition under which the arithmetic and geometric monodromy of the covering are equal ...
3
votes
0answers
139 views

What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And I’m confused with one of its ...
2
votes
3answers
380 views

Can a Decidable Theory Have Non-recursive Models?

Tennenbaums' theorem proves neither addition nor multiplication can be recursive in any countable non-standard model of arithmetic. Tennenbaum's proof applies to theories much weaker than PA. ...
7
votes
0answers
333 views

On the number of polynomials that divide $x^{q-1}-1$ in some subspaces of $\mathbb F_q[x]$

Let $\mathbb F_q$ be a finite field (where $q$ is in general a power of a prime), and let $e, k$ be positive integers with $k \leq e < q-1$. Let $f_0(x), \ldots, f_k(x) \in \mathbb F_q[x]$ be ...
6
votes
3answers
333 views

On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$

Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows $$ S=\left[\begin{array}{ccccccc} 0 & ...
4
votes
1answer
175 views

Cyclic subgroups of GL(n,q)

Let $q$ be a prime power. It is well known that every Singer subgroup (subgroup of order $q^n-1$) in $GL(n,q)$ are conjugate. My question is: If $H$ is a cyclic subgroup of order $m$ in $GL(n,q)$, ...
2
votes
1answer
172 views

Model of hyperbolic geometry with finite number of parallel line

Does there exist a model of hyperbolic geometry such that only finite number of distinct parallel lines through a point which does not intersect given line? Edit (Misha): I usually do not edit other ...
2
votes
1answer
136 views

Ranks of higher incidence matrices of designs

In 1978 Doyen, Hubaut and Vandensavel proved that if $S$ is a Steiner triple system $S(2,3,v)$ then the $GF(2)$ rank of its incidence matrix $N$ is $$ Rk_{2}(N)=v-(d_{p}+1), $$ where $d_{p}$ is the ...
2
votes
1answer
191 views

$\text{mod} \, p^2$ trace identity

Let $p$ be a prime, and let $\text{GL}_n \big( \Bbb{Z} / p^2 \Bbb{Z} \big)$ be the group of $n \times n$ invertible matrices over the ring $\Bbb{Z} / p^2 \Bbb{Z}$. Does there exist a positive integer ...
4
votes
1answer
258 views

Full-rank rectangular matrices over GF(2)

Given positive integers $k$, $m$, $n$, let $A$ be an $m \times n$ matrix over $GF(2)$ constructed as follows. Let $X_1, \ldots, X_m$ be independent random subsets of $\{1,\ldots,n\}$ with cardinality ...