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