2
$\begingroup$

Given an oracle that can compute $g^{x^{-1}}\bmod p$ from $g^x\bmod p$ is it possible to compute $g^{x^2}\bmod p$ in polynomial time ($p$ is a prime and $g$ generates the multiplicative group modulo $p$)?

$\endgroup$
2

2 Answers 2

4
$\begingroup$

Well, if the Oracle works with an arbitrary base 'g', then it is easy.

If we give the Oracle the base $g^x$, and ask it to 'invert' $g$ with respect to that base, that is:

The base is $h = g^x$

The value being inverted is $g = h^{x^{-1}}$

Hence, the Oracle will return the value $h^{{x^{-1}}^{-1}} = h^x = g^{x^2}$

And we're done...

$\endgroup$
4
  • $\begingroup$ "The value being inverted is g=h^{x^{−1}}".. We are not given h^x. $\endgroup$
    – Turbo
    May 14 at 18:35
  • $\begingroup$ @Turbo: no, we're not - that's the value that the Oracle gives us... $\endgroup$
    – poncho
    May 14 at 19:06
  • $\begingroup$ I don't follow. What is the input to the oracle to get $h^{x^{-1}}$? $\endgroup$
    – Turbo
    May 14 at 22:20
  • $\begingroup$ @Turbo: the input is $g$; it happens that $g = h^{x^{-1}}$ $\endgroup$
    – poncho
    May 15 at 1:19
3
$\begingroup$

If the oracle is restricted to working with $g$ as the base, then the reduction is possible by considering the following equality: $$\frac{1}{x-1} - \frac{1}{x} = \frac{1}{x^2 - x}.$$

Inversions in the exponents are implemented by the oracles, while the other operations are done by multiplications/divisions.

$\endgroup$
1
  • $\begingroup$ This is a better answer than mine... $\endgroup$
    – poncho
    May 20 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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