two number theory questions

[Anton Stiglic]

----- Original Message -----
From: "Steve Zhang" <steve9482003 at yahoo.com>

> Question #1:
>
> Assume that p is a large prime and g is a generator.
>
> Given y=g^b mod p but no b (that is, b is unknown), are there efficient
algorithms to compute z=g^{b^{-1}} mod p?

If you can tell whether of not g^x mod p (for unknown x) is a quadratic
residue or not, then there is a way to
efficiently do what you ask (think about binary extended Euclidean
algorithm).

> Question #2:
>
> Assume that p is a large prime and g is a generator.
>
> Given y=g^{b^2} mod p but no b (that is, b is unknown), are there
efficient algorithms to compute z=g^b mod p? How about computing y from z (b
is still unknown)?

About computing y from z:

You can prove that if for any x, given only g^x (mod p), you can compute
g^(x^2),
then the Diffie-Hellman problem would be easy mod p.

May I ask why are you asking these assignment-like questions?

--Anton




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com