0

If I have g = primitive root and p = prime number such that:

X = $g^x$ mod p

Y = $X^y$ mod p

I know the values of g, p, X, Y. Can I calculate $g^y$ without knowing x? How do I do that?

For example: Let us say I know that g = 5; p = 23; X = $g^x$ mod p = 8; Y = $X^y$ mod p = 2.

I do not know that x = 6 and y = 15. How do I find the values x = 6 and y = 15?

  • Yes. Let us say I know that

    g = 5; p = 23; X = $g^x$ mod p = 8;
    Y = $X^y$ mod p = 2;

    I do not know that x = 6 and y = 15. How do I find the values x = 6 and y = 15?

     –  Oct 08 '22 at 22:37
  • @Moo Thank you for the suggestion. I have added the example. –  Oct 08 '22 at 22:42

1 Answers1

0

Even if you are given $x=1$ [and so $g = X$ is known too], there is still no known efficient algorithm at the writing of this post, to find the remaining unknown variable $y$.

Indeed, if you could, then you'd have an algorithm that finds efficiently, for general instances $p,Y,g$, the integer $y$ that solves the equation $Y=g^y \pmod p$; $Y,p,$ and $g$ known. There is no such algorithm known at this time. See discrete logarithm problem.

Mike
  • 20,434
  • But Y = (g^(xy) )mod p here. So can we still not find $g^y$? –  Oct 08 '22 at 23:38
  • As I already said in my answer above, even if you are given $x=1$ and so $g^y \pmod p =Y$; $Y,g,p$ known, you still cannot efficiently find $y$. – Mike Oct 08 '22 at 23:46
  • I understand. Thank you. –  Oct 09 '22 at 00:55