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 understand that $\omega$ is also a primitive $\phi(N)$-th root of unity modulo $N$.

Knowing the value of $\omega$, is there a fast way, for an arbitrary $n<N$, compute one of the primitive $n$-th roots of unity modulo $N$?

I searched the Wikipedia and didn't find anything, but I could have been inattentive.

  • 2
    $\begingroup$ What do you mean by "Galois field modulo $N$"? Do you mean a finite field of cardinality $N$? If so, then a primitive root will have order $N-1$, not $\phi(N)$. Perhaps you mean instead the multiplicative group of units in the ring ${\mathbb Z}/N{\mathbb Z}$. $\endgroup$ – Greg Martin Jan 30 '12 at 11:38
  • $\begingroup$ $\phi(N)=N-1$ in a finite field, so it should be the same. Yes, I meant finite fields. $\endgroup$ – wh1t3cat1k Jan 30 '12 at 12:11
  • $\begingroup$ You do realize (as in Greg's answer) that $n$ has to be a factor of $N-1$, don't you? Otherwise you need to go to an extension field $GF(N^m)$ and cannot do it all in $GF(N)$. In that case you have to first find the smallest integer $m$ such that $n|N^m-1$. If $n$ has a common factor with $N$, then it cannot be done no matter what. $\endgroup$ – Jyrki Lahtonen Jan 30 '12 at 12:56
  • 1
    $\begingroup$ @wh1t3cat1k $\phi(N) = N-1$ if $N$ is prime, but in general not if $N$ is a power of a prime. $\endgroup$ – Emilio Ferrucci Jan 30 '12 at 13:34
  • 1
    $\begingroup$ My best guess is that you're confusing, for example, the Galois field ${\mathbb F}_9$ with 9 elements with the ring ${\mathbb Z}/9{\mathbb Z}$. Both of their multiplicative groups of units, ${\mathbb F}_9^\times$ and $({\mathbb Z}/9{\mathbb Z})^\times$, are cyclic; but $\#{\mathbb F}_9^\times = 9-1 = 8 \ne \phi(9)$ and $\#({\mathbb Z}/9{\mathbb Z})^\times = \phi(9) = 6$. $\endgroup$ – Greg Martin Jan 31 '12 at 2:02

If you have a generator $\omega$ of any cyclic group (regardless of whether it comes from a field or not), it is easy to construct elements of any order you want. Say the cyclic group (and hence $\omega$ as well) has order $k$. Then for any $d$ dividing $k$ (which are all the possible orders), the element $\omega^{k/d}$ will have order $d$.

Assuming your question is asking about the multiplicative group $({\mathbb Z}/N{\mathbb Z})^\times$, then an element of order $d$ is the same thing as a primitive $d$th root of unity modulo $N$.

  • $\begingroup$ $({\mathbb Z}/N{\mathbb Z})^\times$ is only cyclic if $N$ is the power of an odd prime, or twice the power of an odd prime. Also, if N is the power of a prime, the multiplicative group of $\mathbb{F}_N$ and of $\mathbb{Z}_N$ are two different things (unless N is prime). $\endgroup$ – Emilio Ferrucci Jan 30 '12 at 13:25

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.