# Tagged Questions

52 views

### Counting the roots of a polynomial over a finite field

Let $\mathbb{F}_{11}$ be the field of 11 elements and let $\mathcal{K}$ be the splitting field of $x^{3} - 1$ over $\mathbb{F}_{11}$. How many roots does $(x^{2} - 3)(x^{3} - 3)$ have in ...
45 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, ...
141 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 ...
40 views

### $\sum_{x \in \mathbb Z_9}w^{x^2-cx}=?$,where $c \in \mathbb Z_9$ and $w=e^{2\pi i/9}$

$$\sum_{x \in \mathbb Z_9}w^{x^2-cx}=?$$ where $c \in \mathbb Z_9$, $w=e^{2\pi i/9}$ and $\mathbb Z_9$ is the ring of integers modulo 9.
128 views

### sum of $p$th roots of unity

Let $p$ be an odd prime. Let $\mathbb Z_p$ be the ring of integers from $0$ to $p-1$, i.e. $\mathbb Z_p=\left\{0,1,\dots,p-1\right\}$. Let $r$ be a positive integer. Then, for all values of $p$, is ...
158 views

### How does trigonometry in a Galois field work?

This is a follow-up to this question. I'm interested in doing trigonometry in finite fields on a computer. I do not understand precisely how trigonometric functions are supposed to work in a finite ...
176 views

### Roots of unity in a field generated by a root of a polynomial

The polynomial x^3 − 2 has no roots in F7 and is therefore irreducible in F7[x]. Adjoin a root k to make the field F := F7(k), which will be of degree 3 over F7 and therefore of size 343. The ...
390 views

### Fastest Way to Find order of element in Finite Fields?

Two questions: I use Miller-Rabin to find a prime, p, close to an arbitrary input number (this is very fast). Then I use Floyd's cycle finding algorithm to find the order of a randomly chosen element ...
### Why are generators of $Z^{*}_p, p=c \cdot 2^k + 1$ so small?
I was implementing NTT for long integer multiplication and thus searched for generators of several $Z^{*}_p$ groups where $p=c\cdot 2^k + 1$. I used the algorithm described in Wikipedia which uses ...