1
vote
1answer
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 ...
2
votes
1answer
46 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
149 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 ...
2
votes
2answers
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.
1
vote
0answers
130 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 ...
1
vote
0answers
161 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 ...
0
votes
1answer
177 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 ...
0
votes
1answer
399 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 ...
3
votes
1answer
74 views

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 ...
2
votes
1answer
65 views

Primitive $2^k$-th roots of unity in $GF(p)$

While debugging an NTT implementation I've noticed something. Looks like if I have a primitive $(n = 2^k)$-th root of unity $\omega$ in a $GF(p)$, then $\omega ^0 = -\omega ^{n/2} + p,$ $\omega ^1 = ...
2
votes
1answer
138 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 ...
1
vote
1answer
619 views

Finding primitive $n$-th root of unity modulo $N$ having a primitive root

I'm pretty new to modular arithmetic and not having a good knowledge of algebra, so sorry for perhaps a basic question. Suppose that I have a Galois field modulo $N$ and a primitive root $\omega$. I ...