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$?


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.

| improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.