# Is it possible to decide the base of a discrete logarithm?

Given $R$, a prime $p$ and two bases $g_1$ and $g_2$, is it possible to decide if $R = g_1^r$ mod $p$ or $R = g_2^r$ mod $p$ without knowing $r$?

-
That is at least as hard as the subgroup decision problem. $\;$ – Ricky Demer Oct 25 '13 at 5:04
The subgroup decision problem is quite similar, but with an RSA modulus. The subgroup decision problem can be easy mod prime $p$, if p-1 can be factorized – tylo Oct 25 '13 at 12:00

It's obviously possible to decide if $R=g_1^r\mod p$ or $R=g_1^r \mod p$ simply by computing successive powers of $g_1$ and $g_2$ until either $R$ is matched or $g_1$ or $g_2$ respectively is reached. However this is slow.

We can call $g_1$ and $g_2$ "generators" and the set of all values $g^x \mod p$ the "subgroup generated by $g$". You can find $R=g^x$ if and only if $R$ is a member of the subgroup generated by $g$. The number of elements of the subgroup is the "order" of $g$ and a factor of $p-1$

If $g$ is a quadratic residue mod $p$ (i.e it is possible to find an $x$ such that $g=x^2 \mod p$) and $R$ is not a quadratic residue then it's not possible that $R=g^r$. It's possible to determine very quickly (by calculating the legendre symbol) whether a number is a quadratic residue or not for any prime.

This generalises to cubic etc residues for suitable primes.

As Ricky Derner mentions in a comment, the problem is a staple of cryptographic constructions and can be made easy or hard based on the factorization of $p-1$ and the order of $g$.

-
@tylo In your answer you say "this is not decidable" which is wrong and your answer just replicates a small portion of my answer. Did you read it? – Bytecoin Oct 25 '13 at 13:46

Without further knowledge about $g_1$ and $g_2$, this is not decidable.

However, if $g_1$ and $g_2$ are generating the same subgroup, then there is a value $r$ for each base: $R=g_1^{r_1}$ and $R=g_2^{r_2}$ (Assuming, R is in this subgroup as well).

-