0
$\begingroup$

I have an exercise that says the following:
Let $p$ be an odd prime, and let $a$ and $b$ be generators $\mathbb{Z}​_p^*$. Suppose that we have an efficient algorithm $A$ for computing discrete logarithms with base $a$. Show how this algorithm can be used to efficiently compute discrete logarithms with base $b$.

With considering a change of base rule, I have done the following:

B(b,x):
    return A(x) / A(b)

Is this correct and the end of the exercise? I would say that it is, but this is very easy compared to the other exercise I'm currently solving, so I think that I have missed something...

$\endgroup$
2
  • $\begingroup$ And, exercise = Homework? $\endgroup$
    – kelalaka
    Dec 18 '20 at 20:27
  • 2
    $\begingroup$ We've got a policy of only hinting for homework questions, hence this question is often relevant for handling it. We generally don't close them (directly) if indication of effort is given and your question does show effort. $\endgroup$
    – Maarten Bodewes
    Dec 19 '20 at 0:49
1
$\begingroup$

Is this correct and the end of the exercise?

I can't say to what extent your professor wants you to be explicit, but it is essentially correct (and I'd accept it as an answer if I were grading it). Now, your professor may be expecting you to explain (or give a proof) why this is correct.

$\endgroup$
4
  • $\begingroup$ This is correct because the base change formula for ordinary logarithms is also valid for discrete logarithms. Or is there more to explain, why this holds? $\endgroup$
    – Jan
    Dec 18 '20 at 20:23
  • 1
    $\begingroup$ @Ziga: you have to be a bit careful about arguments from analogy - not everything true for "standard" (real) logarithms are also true for discrete logs, but this is. It might be good if you could write out why... $\endgroup$
    – poncho
    Dec 18 '20 at 20:33
  • $\begingroup$ I guess if I had pupils beyond my relatives, they'd prefer your grading to mine. $\endgroup$
    – fgrieu
    Dec 19 '20 at 7:04
  • $\begingroup$ OK, so I'm still trying to prove that the change of base rule holds for discrete logarithm, but I'm stuck, so I have a question. If $a$ and $b$ are generators of $\mathbb{Z}_p^*$, where $p$ is an odd prime, does it hold, that if $k=\log_a b$ then $k\in \mathbb{Z}_p^*$? $\endgroup$
    – Jan
    Dec 19 '20 at 23:53
1
$\begingroup$

For me, some things are slightly incorrect or missing:

  • If $B$ is an algorithm to “compute discrete logarithms with base $b$”, it does not need an input $b$ (much like $A$ has no input for $a$).
  • It is not detailed exactly what the / operation does, and that's far from trivial. Take $p=2311$, $a=53$, $b=3$, $x=5$. $A(x)\mapsto322$, $A(b)\mapsto989$. How exactly do we find that $B(x)\mapsto1988$ from $322/989$ ?
  • If $A$ works with sufficient probability (including, always), does $B$ work with sufficient probability (or if applicable, always) in order to match what it is asked to prove?
  • It is not told why $B$ is efficient.
$\endgroup$
4
  • $\begingroup$ By your example, it looks like calculations with discrete logarithm are performed by $\bmod{2310}$. Does this mean, that if I have a group $\mathbb{Z}_p^*$, then all calculations with discrete logarithms will be done by $\bmod{p-1}$? To clarify, group $\mathbb{Z}_p^*$ is a group of all invertible elements from group $\mathbb{Z}_p$, and because for my example $p$ is an odd prime, that means that $\mathbb{Z}_p^*=\{1,2,\ldots , p-1\}$. $\endgroup$
    – Jan
    Dec 20 '20 at 14:09
  • $\begingroup$ @Ziga: operation on discrete logs can be performed modulo the order of the group, that is$\pmod{\varphi(p)}$ for group $\mathbb{Z}_p^*$ (where $\varphi$ is the Euler totient function), that is$\pmod{(p-1)}$ when $p$ is prime. If we restrict to power of an element, we can reduce modulo the order of the element (which divides the order of the group). $\endgroup$
    – fgrieu
    Dec 20 '20 at 14:18
  • $\begingroup$ So, this answer, where user @kelalaka suggested that operations with discrete logarithm are performed by $\bmod p$ is wrong? $\endgroup$
    – Jan
    Dec 20 '20 at 14:39
  • 1
    $\begingroup$ @Ziga: Things are too complicated for a comment. I made an answer. $\endgroup$
    – fgrieu
    Dec 20 '20 at 20:57

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.