Finding discrete logs if we know discrete logs in different base

Question

Suppose you have an efficient algorithm for calculating discrete logs in some base "a" would it be possible to use this algorithm to find discrete logs in a different base for which we don't know an efficient algorithm ? And if yes, how ?

Answer 1

If $a$ generates the same sized subgroup as the different base $g$, then yes, it's easy. Note: in $Z_p^*$, there's only one subgroup of a given size, so if $a$ and $g$ generate the same sized subgoup, they must generate the same group, and hence $a^y = g$ for some $y$).

To solve the problem $g^x = h$, we first solve $a^y = g$ and $a^z = h$ (which are both easy, they're problems with our preferred base. We then know $a^{xy} = a^z$, or $xy = z \pmod{p-1}$ (or $\pmod{q}$ if you know the size of the subgroup $q$); computing $x = y^{-1}z \pmod {p-1}$ is easy.

If $g$ generates a supergroup of $a$ that's only slightly larger, then this can be solved as well; if $g$ generates a significantly larger subgroup (e.g. the subgroup that $a$ generates is tiny), then this isn't of much help.