[13133] in cryptography@c2.net mail archive
Re: two number theory questions
daemon@ATHENA.MIT.EDU (Anton Stiglic)
Mon Apr 28 13:37:27 2003
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: "Anton Stiglic" <astiglic@okiok.com>
To: "Steve Zhang" <steve9482003@yahoo.com>,
<cryptography@metzdowd.com>
Date: Mon, 28 Apr 2003 13:25:27 -0400
----- Original Message -----
From: "Steve Zhang" <steve9482003@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@metzdowd.com
