Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|improve this question
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
up vote 0 down vote accepted

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$.

share|improve this answer
@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).

share|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.