Assume $\mathbb{Z}^*_p = \{1,2,\dots, p-1\}$ with operation of multiplication modulo $p$, $p$ prime and let $g$ be a generator of this group.
- If $d$ divides $p - 1 $, find a $b \in \mathbb{Z}^*_p$ with $\text{ord}(b) = d$
- How many elements of order $d$ exist in $\mathbb{Z}^*_p$ ?
- How many generators has the cyclic subgroup generated by $b$ with $\text{ord}(b) = d$?
- How many cyclic subgroups of order $d$ exist in $\mathbb{Z}^*_p$?
- If you're given an element $h$, its order $d$ and a random element $a$, how can you check if $a$ belong in the subgroup generated by $h$ in polynomial time?
Solution:
$f: \mathbb{Z}_{p-1} \longrightarrow \mathbb{Z}^*_p$ with $f(x) = g^x \pmod{p}$ is an isomorphism. Also, in $\mathbb{Z}_{p-1}$ the element $\frac{p-1}{d}$ is of order $d$. Thus, $g^{\frac{p-1}{d}} \pmod{p}$ is of order $d$ in $\mathbb{Z}^*_p$.
Only one, since $f$ is an isomorphism and $\frac{p-1}{d}$ is the only element of order $d$ in $\mathbb{Z}_{p-1}$
This subgroup has order $d$ and thus $\varphi(d)$ generators (all the coprimes less than $d$)
Only one, with generator $\frac{p-1}{d}$
Check: $h^0 = a$ or $h^1 = a$ or $h^2 = a$ or $\dots$ or $h^{d-1} = a$. If one of the equalities is true, then $a$ belongs in the subgroup generated by $h$. In any other case, it doesn't.
Please, if you can, confirm my solution.
You have one mistake that you haven't noticed. On the elements of order $d$ in $\mathbb{Z}_p^*$, you are right about the isomorphism between $(\mathbb{Z}_{p-1},+)$ and $\mathbb{Z}_p^*$, but you're missing there are more elements of order $d$ in $\mathbb{Z}_{p-1}$. I'll leave you with a hint: Consider $\frac{(d-1)(p-1)}{d}$, what is its order in $\mathbb{Z}_{p-1}$? After you answer this question, I wish you may have a greater insight in the problem.