I need help with the following problem: We have 2 prime numbers $p,q$ such that $p = 2q+1$. We are given 2 numbers - $g_1,g_2$ and we need to verify that $g_1, g_2 \in \mathbb{Z}_p^*$ and that they are generators of a sub-group of $\mathbb{Z}_p^*$ of order q.

How can we do this efficiently?

So far I came up with the direction of Euler's theorem: I thought that I need to check if $g_i^q=1$ - but it should be modulo something and I'm not sure what. To state this more clearly - if I know that for some n $q=\varphi (n)$ and that $g_i$ and $n$ are co-prime, I'd know that it is enough to check that $g_i^q=1 \pmod n$. I'd appreciate some help.. thanks

  • $\begingroup$ You want $g_i^q \equiv 1 \bmod p$. $\endgroup$ – Derek Holt Jan 4 '18 at 8:46
  • $\begingroup$ why $\mod p$? (I don't claim that it's wrong, just need explanation...) $\endgroup$ – noamgot Jan 4 '18 at 10:03
  • $\begingroup$ In addition - why does it prove that there's no $q' < q$ such that $g_i^{q'} = 1 \pmod p$? $\endgroup$ – noamgot Jan 4 '18 at 10:24
  • $\begingroup$ It is mod $p$ by definition: you are working in the group $Z_p^*$. For the second question it's because $q$ is prime. $\endgroup$ – Derek Holt Jan 4 '18 at 12:04

Your Answer

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

Browse other questions tagged or ask your own question.