It is know that given a large prime $p$ and a primitive root of $\mathbb{Z}_p^*$, $g$, and two numbers $g^x$ and $g^y$ (modulo $p$), it's impossible to distinguish $g^{xy}$ from $g^r$ where $x$, $y$ and $r$ are three randomly chosen positive intergers under $p$.
However, in some scenarios, if $x$, $y$ and $r$ are carefully chosen, the above statement may not be that right, meaning that some attributes of $g^{xy}$ may be deduced from $g^x$ and $g^y$, and when $g^r$ does not have one of those attributes, it can be quickly told apart from the "real" $g^{xy}$.
The above is what a friend told me. He also mentioned Fermat's little theorem, which I can't really integrate into the solving of this problem.
Any hints?
Sample data (from a Python script):
p = 71
gx = 67
gy = 9
g1 = 27
g2 = 17
The one thing that comes to mind is checking for quadratic residues.
For any element of $a \in \mathbb Z_p^*$, $a^{\frac{p-1}{2}}$ is either $-1$ or $1$. (In fact, it is $1$ if $a$ is a quadratic residue, and $-1$ otherwise.)
Computing this for $g^x$ and $g^y$ in your sample data, we get $(g^x)^{\frac{p-1}{2}} = -1$ and $(g^y)^{\frac{p-1}{2}} = 1$. So we must have $(g^{xy})^{\frac{p-1}{2}} = g^{x \cdot y\cdot \frac{p-1}{2}} = ((g^y)^{\frac{p-1}{2}})^x = 1^x = 1$. Since $g_1^{\frac{p-1}{2}} = 1$ and $g_2^{\frac{p-1}{2}} = -1$, we know that $g_1 = g^{xy}$ and $g_2$ is a fake.
Equivalently, computing $(g^x)^{\frac{p-1}{2}}$ tests if $x$ is even or odd. (Even powers of $g$ are precisely the quadratic residues in $\mathbb Z_p^*$.) Having figured out whether $x$ and $y$ are even or odd, we can always decide if $xy$ will be even or odd, so $r$ had better have the same parity or we'll be able to tell $g^{xy}$ apart from $g^r$.
If $p >2$, then $p-1$ is guaranteed to be even, so we can always play the parity game. If $p-1$ has other small prime factors, then we have a chance at exploiting those, too, which is one of the reasons why standard advice is to choose $p$ such that $\frac{p-1}{2}$ is also prime.