What is $\Bbb Z_p^*$ in this scenario?

Question

Let $\alpha$ be an element of order $q$ in $\Bbb Z_p^*$, where $p$ is a large prime number such that $p-1$ has large prime factor $q$. Also, what it means by order?

Answer 1

$\mathbb{Z}_p^{\ast} = \mathbb{Z}_p \setminus \{0\}$, which is a group under muliplication (modulo $p$). The order $o(g)$ of some $g \in G$ where $(G, \cdot, 1)$ is any finite group, is just $o(g) = \min \{n \in \mathbb{N}^+: g^n = 1\}$

(which exists by well-orderedness of the naturals and finiteness of $G$: we just keep taking powers of $g$ until we reach a repeated element $g^k = g^l$ for some $k < l$ and then $g^{l-k} = 1$. So the set we take a minimum of is non-empty.) (nice fact: $o(g)$ is always a divisor of the group size $|G|$)

We then have that $\{g, g^2, g^3, \ldots ,g^{o(g)}=1\}$ is the subgroup generated by $g$. In this subgroup every element has a logarithm over $g$, by definition $\log_g(g^k) = k$, and in a large group finding the logarithm of some arbitary element in it (bu not given as $g^k$ of course) is a supposedly hard problem. So you need elements of large order. In fact in $\mathbb{Z}_p^\ast$ which has size $p-1$, there are even elements of order $p-1$ and also of every divisor of $p-1$, so e.g. of order $q$. These groups generated by such elements are then used in Diffie-Helman protocols, etc. to link it back to cryptography.