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$.

  • $\begingroup$ $1$ is always a $n$th root of unity, for any $n$, in any field. Also, how does this relate to cryptography? $\endgroup$ – fkraiem May 19 '19 at 20:37
  • $\begingroup$ @fkraiem: well, sometimes in ring lattices, we at times use the NFT algorithm to speed ring multiplies - that uses a large root of unity... $\endgroup$ – 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}$)

| improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – irakliy May 19 '19 at 20:08
  • 1
    $\begingroup$ @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) $\endgroup$ – poncho May 19 '19 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.