Tagged Questions
1
vote
0answers
68 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
67 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
88 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
64 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
51 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
89 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
380 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 ...
