# Finding a prime field with n-th roots of unity

How can I find the smallest prime $$p$$, such that field $$GF(p)$$ has $$n$$-th roots of unity?

For example, I know that for $$p=2^{256} - 351 \times 2^{32} + 1$$ there exit roots of unity for $$n=2^{32}$$. But I don't know if there is a smaller $$p$$ that would have the same "order" for the roots of unity, or how to find smallest prime $$p$$ for a specific $$n$$.

If it makes things easier, for my purposes, $$n$$ can always be a power of $$2$$.

• $1$ is always a $n$th root of unity, for any $n$, in any field. Also, how does this relate to cryptography? – fkraiem May 19 '19 at 20:37
• @fkraiem: well, sometimes in ring lattices, we at times use the NFT algorithm to speed ring multiplies - that uses a large root of unity... – poncho May 19 '19 at 21:07

How can I find the smallest prime $$p$$, such that field $$GF(p)$$ has $$n$$-th roots of unity?
Any prime of the form $$kn + 1$$ has $$n$$-th roots of unity; we know this because the group $$\mathbb{Z}_p^*$$ (for prime $$p$$) is a cyclic group of order $$p-1$$, hence for all the factors of $$p-1$$, including $$(p-1)/k$$, it has elements of that order (at least, if you don't count values of $$p$$ which have $$2^{31}$$th roots of unity, but not elements of order $$2^{32}$$)
A quick search shows that $$18 \cdot 2^{32} + 1 = 77309411329$$ is the smallest prime of that form, hence that is your answer.
A quick computation shows $$45467087722 ^ {2^{32}} \equiv 1 \pmod{77309411329}$$, that is, it is a $$2^{32}$$th root of unity (and more specifically, it has order $$2^{32}$$)
• Thank you! So, basically, I pick $n$ and then just try different values for $k$ until I get $kn+1$ that is a prime, right? – irakliy May 19 '19 at 20:08
• @irakliy: pretty much, yes. Then, to find an element $e$ of order $n$, you pick a random $r$, compute $e = r^k \bmod p$, and then verify that $e^{n/2} \not\equiv 1 \pmod p$, if so, then $e$ is your element (you need extra checks if $n$ is not a power of 2) – poncho May 19 '19 at 20:20