# Discrete Log solve using Index-Calculus producing incorrect 'r' value.

I have a discrete log that I need to solve to aid in a Cryptography problem, that deals with both programming and mathematics, so I was unsure where to post this problem, feel free to move me if needed. I must use Index-Calculus to solve this discrete log. Here's the setup, my attempt, and my code (producing the wrong 'r' value).

Let $$p=10007$$. $$5$$ is a primitive root. It can be shown that $$L_5(2)=6578, L_5(3)=6190, L_5(7)=1301$$. Use these facts to find $$L_5(100)$$

So, I have the fact that

$$100\times5^r\equiv7\times3\times2\mod 10007$$

$$\implies L_5(100)\equiv-r+L_5(7)+L_5(3)+L_5(2)\mod 10006$$

And $$L_5(7)+L_5(3)+L_5(2)$$ are known, so I now just need to find a $$r$$ s.t.

$$100\times5^r\equiv7\times3\times2\equiv42\mod 10007$$

So I wrote a program that basically just loops through $$j$$ for $$0\leqslant j\lt p$$, and then calculates $$100*5^j\equiv ans \mod 10007$$ and checks if $$ans = 42$$. When it is equal to 42, it prints the j used. This is producing an answer of $$r=j=378$$, however this is NOT correct, as $$100\times5^{378}\not\equiv 42\mod 10007$$. The correct answer is $$r=j=911$$.

Where have I gone wrong? Or else, is there an easier way to solve this problem? (Using Index-Calculus, I can solve it using Baby Step Giant Step, or Pohlig-Hellman algorithm.

• It seems you aren't clear about how discrete logs work. If my answer doesn't help clarify that then let me know and I can elaborate. – Bill Dubuque Mar 27 '19 at 23:14

$$100 = 2^2 \cdot 5^2$$. If $$2 \equiv 5^{6578} \bmod p$$, then $$2^2 \cdot 5^2 \equiv 5^{2 \cdot 6578 + 2} \equiv 5^{3152}\bmod p$$.
It is called a discrete log because $$\,L(xy)\equiv L(x)+L(y)\ \pmod{p\!-\!1},\$$ therefore
\begin{align} L(2)&\,\equiv\, 6579,\, L(5)\equiv 1\\[.2em] \Rightarrow\, L((2\cdot 5)^2) &\,\equiv\, 2(L(2)+L(5)) \\[.2em] &\equiv\, 2(6578+1)\end{align}\qquad \qquad\qquad\quad\!
Remark  While you can ignore the logs and instead work with powers of $$5$$ as in Robert's answer, this likely is completely opposite of the goal of the exercise, which is likely intended to teach you how to convert such multiplicative problems into simpler additive problems in $$\,\Bbb Z_{p-1} =$$ integers $$\bmod p\!-\!1\$$ (which the raison d'etre of this index calculus).
• Whether you write it as $L(2^2 \cdot 5^2) = 2 L(2) + 2$ or $2^2 \cdot 5^2 = 5^{2 \cdot L(2) + 2}$ is a matter of taste. The actual computation is the same. – Robert Israel Mar 27 '19 at 22:53