# Tagged Questions

42 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 ...
71 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. ...
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, ...
53 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$. ...
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 ...
40 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$?
122 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 ...
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 ...
119 views

86 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$ ...
132 views

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) ...
106 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. ...
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$. ...
112 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}$? ...
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 ...
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 ...
256 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 ...
95 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$ ...
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?
139 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$ ...
120 views

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 ...
69 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
80 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 ...
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 ...
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 ...
99 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!
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}$ $|$ ...
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$?
975 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 ...
608 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 ...
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 ...
296 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 ...
1k views

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 ... 1answer 129 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 ... 1answer 133 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 = ...
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 ...