1
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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