1
$\begingroup$

I'm given a prime number $p = 1217$

I'm also given the following equations:

$$ 40 \equiv \log2 \pmod{64} \\ 63 \equiv \log3 \pmod{64} \\ 13 \equiv \log5 \pmod{64} \\ 13 \equiv \log2 \pmod{19} \\ 10 \equiv \log3 \pmod{19} \\ 01 \equiv \log5 \pmod{19} $$

The question asks to give the answers to

$$ \log 2 \pmod{p-1} \\ \log 3 \pmod{p-1} \\ \log 5 \pmod{p-1} $$

I know the answers are $488, 447, 77$ respectively.

And I know they are the Discrete Logarithms of $2,3,5$ respectively.

However there is no other explanation of how to get this answer.

I've observed that $1216$ is the Lowest common multiple of $64$ and $19$.

I also think the Chinese remainder theorem might be useful here.

It bothers me that we don't know the base of the logarithms and this makes me totally confused.

I would hugely appreciate an explanation on what's going on here, I don't fully understand what the question is asking, let alone how they got to their answer.

$\endgroup$
  • 3
    $\begingroup$ Ignore the base of the logarithms. Instead, treat $\log 2$ as an unknown variable whose value you're trying to determine. $\endgroup$ – poncho Apr 20 '16 at 23:20
  • 2
    $\begingroup$ Hint: observe that $p-1$ is the product of $u=64$ and $v=19$, and $\gcd(u,v)=1$, and you know the unknowns ($\log2$, $\log3$, and $\log5$) modulo $u$ and modulo $v$; now apply the Chinese Remainder Theorem. $\endgroup$ – fgrieu Apr 21 '16 at 10:07

Your Answer

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

Browse other questions tagged or ask your own question.