Understanding the Pohlig-Hellman algorithm

Question

The paper has the following relation: $$y^{(p-1)/p_i} \equiv \alpha^{x(p-1)/p_i} \equiv \gamma_i^x \equiv \gamma_i^{b_0} \pmod p$$

where $\gamma_i = \alpha^{(p-1)/p_i}$. I understand this relation and can show how each step is derived. However I'm stuck at the next step. From the paper:

$\gamma_i$ is primitive $p_i$th root of unity. There are therefore only $p_i$ possible values for $y^{(p-1)/p_i} \pmod p$, and the resultant value uniquely determines $b_0$

What exactly does this mean and how do I get $b_0$ from $\gamma_i$?

Answer 1

Note that $\alpha$ is a primitive element in $GF(p)$ and $\gamma_i$ is a generator of a subgroup $G_i\subseteq GF(p)$ with order $p_i$, i.e., $G_i=\{\alpha^{(p-1)/p_i},\alpha^{2(p-1)/p_i},\ldots,\alpha^{p_i(p-1)/p_i}(=1)\}$. Since $y^{(p-1)/p_i}\in G_i$, there exists a unique value $b_0\in \mathbb{Z}_{p_i}$ such that $y^{(p-1)/p_i}=\gamma_i^{b_{0}}$. To compute $b_0$, you can for instance apply the baby-step giant-step algorithm.