I have a prime $p = 7$ and was tasked to select a random value in $\mathbb Z_p^*$ in my signature scheme.

What does the full range of $\mathbb Z_p^*$ contain in this case?

Is it $\{0...7\}$ or $\{0...6\}$ or $\{1...6\}$ or $\{1...7\}$?

  • $\begingroup$ This question is purely mathematical (I known, $\mathbb Z_p^*$ is often used in cryptographics). Better move it to math.stackexchange.com? $\endgroup$ – Thekwasti Nov 11 '14 at 7:57
  • $\begingroup$ I overlooked, that this question is raised from a signature scheme... But still, the question itself is pure mathematics. $\endgroup$ – Thekwasti Nov 11 '14 at 8:03

It contains the equivalence classes represented by $\{1,\ldots,6\}$.

To elaborate on Nova's comment below, $\mathbb{Z}_p$ is the collection of congruence classes when you divide by $p$. When $p=7$, two integers represent the same congruence class when they have the same remainder when divided by $7$. As you probably know, the only possible remainders are $\{0,1,\ldots,6\}$.

In particular, if $n$ is an integer and $0\leq n\leq 6$, then the remainder of $n$ divided by $7$ is $n$ itself. This means that any integer represents the same congruence class as its remainder does.

I hope you can figure out the rest from here, since you should know that the nonzero congruence classes have inverses and the only non-invertible congruence class is the one represented by $0$, hence my original answer.

  • 1
    $\begingroup$ Would be nice if you could explain the answer a bit. I know why this is the case, but we should not just answer the question. Explaining the case behind this would be advantageous. $\endgroup$ – Nova Nov 9 '14 at 3:52
  • $\begingroup$ Nive improvement. I upvoted your answer. $\endgroup$ – Nova Nov 11 '14 at 6:54

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.