Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Let $p$ be a prime number, $g, h$ be generators of the cyclic group $Z^{*}_{p}$ , and $f$ be defined as:

$f : \lbrace 1, . . . , p − 1\rbrace^{2} → Z^{∗}_{p}; (x,y) \rightarrow g^{x}h^{y}\;mod\;p$.

Let $(x_{1} , y_{1} ), (x_{2} , y_{2})\in \lbrace 1, . . . , p − 1\rbrace^{2}$ with $(x_{1} , y_{1} ) \neq (x_{2} , y_{2} )$ and $f (x_{1} , y_{1} ) =f (x_{2} , y_{2} )$.

I need to prove that the discrete logarithm $log_{g}(h)$ mod p can be computed efficiently.

thank you very much for any help or hints

share|improve this question
1  
I don't believe this is the case. Take $(x_1,y_1)=(1,1)$ and $(x_2,y_2) = (\frac{p+1}2,\frac{p+1}2)$; then $g^{x_2} = g\cdot g^{(p-1)/2} \equiv -g\pmod p$ and similarly $h^{y_2} \equiv -h \pmod p$, so $f(x_1,y_1) = f(x_2,y_2)$. But you haven't learned anything. – Greg Martin Nov 21 '12 at 8:28
1  
To extend @GregMartin's excellent remark a bit: the equation $f(x_1,y_1)=f(x_2,y_2)$ gives you a congruence modulo $p-1$. The coefficient of the unknown logarithm will be $d=y_2-y_1$. You can only make progress, if $d$ does not have large common factors with $p-1$. – Jyrki Lahtonen Nov 21 '12 at 8:59

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.