0
votes
0answers
155 views

Evaluating a polynomial at a root of unity?

Let $R = \mathbb{Z}[x]/(x^n+1)$ be the $2n$th cyclotomic ring (for $n$ a power of $2$ in which case $\Phi_{2n}(x) = x^n+1$). Let $g$ be an $n$-dimensional vector chosen at random from $\mathbb{Z}^n$ ...
3
votes
1answer
71 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 ...