1
vote
0answers
40 views

Bounds for the norm of certain additive character sums

Let $q$ be a power of a prime, let $\alpha$ be a primitive element in the finite field with $q$ elements and let $\chi$ be the canonical additive character of the field. Recently I became interested ...
1
vote
1answer
65 views

Number of points on an elliptic curve over $ \mathbb{F}_{q} $.

I have the following elliptic curve: $$ E: \quad Y^{2} = X^{3} + 1 ~ \text{over} ~ \mathbb{F}_{q}, ~ \text{where} ~ q \equiv 1 ~ (\text{mod} ~ 3). $$ I want to know the number of points on this curve. ...
2
votes
1answer
43 views

The existence of primitive algebraic units modulo 3

Consider the problem of computing $$\sqrt{2} \mod 3 $$ Whereas we seek a number $n$ such that $n^2 \equiv 2 \mod 3$ and furthermore it is known that both $n$ and $2n$ will satisfy this property, ...
3
votes
1answer
50 views

Additive character sum of primitive elements over finite fields

Let $\mathbb{F}_q$ be a finite field with $q$ elements and multiplicative generator $\alpha$, let $\chi$ be a non-trivial additive character of $\mathbb{F}_q$, and let $N$ be a divisor of $q-1$. ...
2
votes
1answer
84 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
39 views

Roots of Artin-Schreier equation

Let $a \in \mathbb F_q, q=p^f$. Is it true that $x^p-x-a$ has a root in $\mathbb F_q$ iff $tr_{\mathbb F_q/\mathbb F_p}a=0$?
3
votes
1answer
121 views

Properties of a sum over the root-of-unity expression of polynomials over a finite field

Consider a bivariate polynomial over the finite field $\mathbb{Z}_n$ of the form: $$f(x,y) = c\cdot xy + g(y)$$ where $c$ is some non-zero constant and $g$ is some univariate polynomial. Let ...
4
votes
1answer
88 views

How do we distinguish between characteristic 0 and characteristic p for very large p?

This is a somewhat soft question, apologies if it turns out to be trivial/nonsensical. Background: I was half-asleep one morning, not quite through my first cup of coffee, and thought about the ...
11
votes
0answers
116 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) ...
1
vote
1answer
58 views

Find the number of 3 x 3 matrices with elements in F_p such that determinant is non zero?

My question is: How do I find the number of $3 \times 3$ matrices $A$ with elements in $F_p$ such that the determinant is non-zero? I don't really now how to go at it. I have a feeling that maybe ...
1
vote
1answer
102 views

Count the primitive polynomials of degree $d$ over $F_{2}$

I am trying to solve an exercise, where i have to determine the number of the primitive polynomials of degree $10$ over the finite field $F_{2}$. My approach was using the formula $\frac{\varphi ...
2
votes
1answer
85 views

Number of points on $Y^2 = X^3 + A$ over $\mathbb{F}_p$

Let $p\equiv 2\pmod{3}$ be prime and let $A\in\mathbb{F}^{∗}_p$ . Show that the number of points (including the point at infinity) on the curve $Y^2 = X^ 3 + A$ over $\mathbb{F}_ p$ is exactly $p + 1$ ...
2
votes
1answer
132 views

Show that $ \sum q^{-\deg \ p(x)} $ diverges

Show that $\sum q^{-\deg \ p(x)}$ diverges, where the sum is over all monic irreducibles $p(x)$ in $K\left[x\right]$, where $k$ is finite field with $q$ elements. First show that $\sum q^{-\deg ...
2
votes
1answer
92 views

Cauchy-Davenport theorem and its extension

According to Cauchy-Davenport Theorem, if $A,B$ are subsets of a prime field ($F_p$) then we have the following bound on the number of elements within the sumset $A + B = \left\{ {\left. {a + b} ...
5
votes
5answers
228 views

Whether the map $x\mapsto x^3$ in a finite field is bijective

Suppose $p\in\mathbb{Z}$ is prime and $\mathbb{F}_p:=\mathbb{Z}/p\mathbb{Z}$ is the finite field of size $p$. Now, consider the map: $$f:\mathbb{F}_p \to \mathbb{F}_p$$ given by $f(x)=x^3$. Then, (1) ...
2
votes
0answers
105 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. ...
4
votes
1answer
56 views

Fix point of squaring numbers mod p

Take the set of integers $\{0, 1, .., p-1\}$, square each element, you get the (smaller) set of quadratic residues. Repeat until you get a fix point set. The size of this set is a function of $p$. ...
1
vote
1answer
111 views

What is the difference between multiplicative group of integers modulo n and a Galois Field

What is the difference between multiplicative group of integers modulo n and a Galois Field? Is $\mathbb{Z}^*_p$ with p prime the same as $GF(p)$? Or is it the same as $\mathbb{Z}/n\mathbb{Z}$? ...
4
votes
2answers
61 views

Linear polynomials of finite fields

I have a final tomorrow, and I was looking over some exercises in my textbook. However, I can't seem to work this problem out. Let $F$ be a field of $p^n$ elements and let $\alpha \in F^*$, where ...
1
vote
1answer
70 views

Solve equations in a field with characteristic p.

Let $p$ be a prime and $K$ a field with characteristic $p$. How to solve the equation $x^2+2=0$ in the field $K$? Here $x, 2, 0 \in K$. Is it equivalent to solve the equation $x^2+2 = 0 \pmod p$? What ...
8
votes
3answers
255 views

Solve $x^3+x \equiv 1 \pmod p$

Find all the primes $p$ so that $$x^3+x \equiv 1 \pmod p \tag{1}$$ has integer solutions. We consider $x$ and $y$ are the same solutions iff $x\equiv y \pmod p.$ We can prove that $(1)$ cannot ...
1
vote
1answer
94 views

Finding quadratic residues in a finite field by using a primitive element

Let $1+2x$ be a primitive element of the field $\mathbb F_9$ obtained via the irreducible polynomial $$x^2 + 1$$ over the base field $\mathbb F_3$. i) Make a list of the elements of $\mathbb F_9$ ...
1
vote
1answer
70 views

Rational and irrational fractions over finite fileds [duplicate]

I've been told that over the field $\mathbb{F}_7$ the square root of $2$ is actually $3$. How come? Why does it happen?
4
votes
2answers
137 views

Polynomial $x^3- xy^3$ and the like over finite fields.

Let $f_{a,n}(x_1,x_2)$ be a polynomial in $\mathbb{F}_p[x_1,x_2]$, where $\mathbb{F}_p$ is a finite field or oder $p$ (perhaps, we may first assume that $p$ is prime) depending on $a\in\mathbb{F}_p$ ...
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 ...
3
votes
1answer
48 views

Representing an element mod $n$ as a product of two primes

Given a positive integer $n$ and $x \in (\mathbb{Z}/n\mathbb{Z})^*$ what is the most efficient way to find primes $q_1,q_2$ st $$q_1q_2 \equiv x \bmod n$$ when $n$ is large? One option is just to ...
11
votes
1answer
152 views

Orientation on finite dimensional vector spaces over finite fields.

For finite-dimensional $\mathbb R$-vector spaces, we define an orientation to be an equivalence class of ordered bases, where $B_1 \sim B_2$ iff the change of basis matrix $A$ taking $B_{1}$ to ...
8
votes
3answers
319 views

Using Hensel's Lemma to Factor a Polynomial over $\mathbb{Z}_4[x]$

We recently learned about codes over $\mathbb{Z}_4$, and Hensel's Lemma. The lemma is as follows: Let $f(x) \in \mathbb{Z}_4[x]$. Suppose $\mu(f(x)) = h_1(x)h_2(x) \cdots h_k(x)$, where $h_1(x), ...
1
vote
1answer
95 views

Largest power of a prime dividing $q^m-1$

For positive integers $x$ and $d$ let $v_d(x)$ be the largest power of $d$ dividing $x$. Let $q>1$, $m$ a natural number, and $l$ a prime dividing $q-1$. Then I want to show that ...
1
vote
0answers
68 views

The mathematics behind Sobol sequences

I am using Sobol sequence as random number generator in a computer program. Beyond just making the program work, I would like to learn the mathematics behind the Sobol sequence (and other ...
15
votes
2answers
473 views

Formula for number of solutions to $x^4+y^4=1$, from Ireland and Rosen #8.18.

There is a sequence of three exercise in Ireland and Rosen's Introduction to Modern Number Theory, Chapter 8, page 106. I can do the first two, but can't finish the third. I can include the proofs to ...
0
votes
1answer
125 views

Formal identity for sum of polynomials over a finite field.

Suppose $F$ is a finite field of order $q$ a prime power. If $f\in F[x]$ of degree $t$, set $|f|=q^t$. Let $\sigma(f)=\sum_{g\mid f}|g|$ where the sum is over the monic divisors of $f$. Why does ...
3
votes
1answer
71 views

Generators for $\mathbb F_p^*$

Let $p$ be prime, then it is a well-known fact that $\mathbb F_p^*= \mathbb F_p -\{0\}$ is a cyclic group under multiplication. Are there any methods to determine the generators of this cyclic or any ...
4
votes
1answer
69 views

Abelian groups related to $(\mathbb{Z}/p\mathbb{Z})^*$, with order close to $p$ — analogous to elliptic curve groups, but simpler

I'm looking for a construction of a group $H$ that is "a sister" to $(\mathbb{Z}/p\mathbb{Z})^*$, in the following rough sense: Each element of $H$ can be represented by one or a few elements of ...
3
votes
2answers
83 views

Are nonsquares actually squares in extensions of even degree?

I was playing around with finite fields, and noticed that if $F$ is a finite field, and $E$ an extension of odd degree, then every nonsquare $a\in F$ is again a nonsquare in $E$. I found this out by ...
2
votes
1answer
79 views

Showing $x^n=\alpha$ has $n$ solutions in a field extension of degree $n$.

Suppose $F$ is a field of cardinality $q$, and $n$ is an integer such that $n\mid q-1$. Now let $K$ be an extension of degree $n$ over $F$. Why does $x^n=\alpha$ have $n$ solutions in $K$ for any ...
1
vote
1answer
48 views

$a(x) \bmod m(x)$ for $m(x) > a(x)$?

Suppose we have polynomials over $GF (2^8)$. $a(x) = x^8$. $m(x) =x^8+x^4+x^3+x+1$ A textbook says that. $x^8 \bmod m(x) = [m(x) - x^8]=(x^4+x^3+x+1)$ So I would like to understand, how do we ...
1
vote
1answer
111 views

Field construction

Explain how to construct a field of order $343$ not using addition and multiplication tables. I understand that every finite field has order $p^n$ for some prime $p$. Since $343$ is $7^3$, let ...
5
votes
1answer
98 views

Irreducible polynomials over $F_q$ with exponents of the form $q^k - 1$.

Let $q$ be some prime power. Is there an explicit family of irreducible polynomials in $F_q[X]$ of the form $\sum_j a_j X^{q^j - 1}$? Thanks!
2
votes
2answers
109 views

Encode the message $[1,1,0,1,1,0,1]$ in BCH code based on the field $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1}$

So here's what I understand so far: $\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1} = GF(16)$ The code is written as $[x^{14},x^{13},x^{12},x^{11},x^{10},x^{9},x^{8}$ $|$ ...
0
votes
1answer
56 views

The probability of sum of $k$ randomly chosen numbers from $\mathbb{Z}_p$ being zero

Let $\{x_i\}_{i \in [k]}$ be randomly chosen independently from the uniform distribution over $\mathbb{Z}_p$. What is the probability that $\Sigma_{i\in [k]} x_i = 0$?
1
vote
1answer
964 views

Proving a polynomial irreducible over finite field [duplicate]

Possible Duplicate: How do I prove that $x^p-x+a$ is irreducible in a field of $p$ elements when $a\neq 0$? How to prove that $x^p - x - 1$ is irreducible over $F_{p}[x]$. I thought ...
0
votes
1answer
604 views

Reed-Solomon Code calculation

I have a Reed-Solomon Code which can correct t=2 errors. The generator polynomial is $p(X) = X^3 + X + 1$ and $p(a) = a^3 + a + 1 = 0$ this means $a^3 = a + 1$ What is the degree of generator ...
10
votes
4answers
278 views

Number of solutions of $x^2_1+\dots+x^2_n=0,$ $x_i\in \Bbb{F}_q.$

Let $\mathbb F$ be field with $q$ element and $\operatorname{char}(\mathbb F)\neq2$. I want to know about the number of solutions of this equation: $$x^2_1+x^2_2+\dots+x^2_n=0 \text{ where } x_i\in ...
5
votes
1answer
293 views

Irreducible factors of $X^p-1$ in $(\mathbb{Z}/q \mathbb{Z})[X]$

Is it possible to determine how many irreducible factors $X^p-1$ in the polynomial ring $(\mathbb{Z}/q \mathbb{Z})[X]$ has and maybe even the degrees of the irreducible factors? ($p,q$ are a primes ...
7
votes
1answer
1k views

Existence of irreducible polynomials over finite field

Let $F$ be a finite field. How do we prove that for each $n \in \mathbb{N}$ there is an irreducible polynomial of degree $n$? One can assume that $F = \mathbb{F}_{p^m}$ where $p$ is prime. If $n \ge ...
2
votes
1answer
128 views

The digit base and the NTT convolution

Suppose I'm using a number theoretic transform (NTT) in an integer field $GF(p)$. I assume that $2n$-th root of unity exists for such a $p$, and I want to compute a convolution of two $n$-length ...
2
votes
1answer
131 views

Discrete log of consecutive numbers

I am trying to understand the relation of additive and multiplicative structure of finite field of prime cardinality. Let's say I have a set that behaves nice additively - an interval $I = ...
5
votes
2answers
294 views

A question on Jacobi sums

I am trying to work through Ireland and Rosen's Number theory book. Following is ex. 26, ch.8(Gauss and Jacobi sums). Let $p$ be a prime. $p\equiv 1\mod{4}$, $\chi$ a multiplicative character of ...
5
votes
2answers
5k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...