Boneh and Venkatesan proposed a problem called the \textit{hidden number problem} and they gave a polynomial time algorithm to solve it. And they showed that one can compute $g^{xy}$ from $g^{x}$ and $g^{y}$ if one has an oracle which computes roughly $\sqrt{\log p}$ most significant bits of $g^{xy}$ from given $g^{x}$ and $g^{y}$ in $ \mathbb F_{p}$ by using an algorithm for solving the hidden number problem. Later, Shparlinski showed that one can compute $g^{x^{2}}$ if one can compute roughly $\sqrt{\log p}$ most significant bits of $g^{x^{2}}$ from given $g^{x}$. In this paper we extend these results by using some improvements on the hidden number problem and the bound of exponential sums. We show that for given $g, g^{\alpha}, \ldots, g^{\alpha^{l}} \in \mathbb F_{\it p}^{*}$, computing about $\sqrt{\log p}$ most significant bits of $g^{\frac{1}{\alpha}}$ is as hard as computing $g^{\frac{1}{\alpha}}$ itself, provided that the multiplicative order of $g$ is prime and not too small. Furthermore, we show that we can do it when $g$ has even much smaller multiplicative order in some special cases.
Boneh와 Venkatesan이 숨겨진 수 문제라 불리는 문제를 제안하였고 이를 풀 수 있는 다항식 시간 알고리즘을 만들었다. 그리고 그들은 $g^{x}$와 $g^{y}$가 주어졌을 때 $g^{xy}$의 대략 $\sqrt{\log p}$ 개 최상위 비트를 계산해주는 오라클이 있다면 숨겨진 수 문제를 푸는 알고리즘을 이용하여 $g^{xy}$를 계산할 수 있다는 것을 보였다. 그 후, Shparlinski는 $g^{x}$가 주어졌을 때 $g^{x^2}$의 대략 $\sqrt{\log p}$ 개 최상위 비트를 계산해주는 오라클이 있다면 $g^{xy}$를 계산할 수 있다는 것을 보였다. 이 논문에서 우리는 숨겨진 수 문제와 지수합의 경계에 대한 향상된 결과를 가지고 이 결과들을 확장하였다. 우리는 $g$의 곱의 위수가 소수이고 너무 작지만 않다면 $g, g^{\alpha}, \ldots, g^{\alpha^l} \in \mathbb F_{p}^{*}$가 주어졌을 때, $g^ {\frac{1}{\alpha}}$의 대략 $\sqrt{\log p}$ 개 최상위 비트를 계산하는 것은 $g^{\frac{1} {\alpha}}$ 자체를 계산하는 것 만큼 어렵다는 것을 보였다. 뿐만 아니라 우리는 특별한 경우에는 $g$가 훨씬 더 작은 곱의 위수를 가지더라도 같은 결론을 얻을 수 있다는 것을 보였다.