I'm supposed to use the following information to solve the question, but I don't know how. $$\begin{align} 19^2 &\equiv 2^3 \times 3^1 \times 5^0 \times 7^0&\pmod{337}\\ 19^5 &\equiv 2^5 \times 3^0 \times 5^1 \times 7^0&\pmod{337}\\ 19^6 &\equiv 2^0 \times 3^0 \times 5^0 \times 7^1&\pmod{337}\\ 19^8 &\equiv 2^3 \times 3^1 \times 5^0 \times 7^1&\pmod{337}\\ 19^{12} &\equiv 2^0 \times 3^0 \times 5^0 \times 7^2&\pmod{337}\\ 19^{18} &\equiv 2^1 \times 3^1 \times 5^0 \times 7^0&\pmod{337}\\ 19^{20} &\equiv 2^4 \times 3^2 \times 5^0 \times 7^0&\pmod{337}\\ 19^{21} &\equiv 2^3 \times 3^0 \times 5^1 \times 7^0&\pmod{337}\\ 19^{24} &\equiv 2^1 \times 3^1 \times 5^0 \times 7^1&\pmod{337}\\ 19^{27} &\equiv 2^3 \times 3^0 \times 5^1 \times 7^1&\pmod{337}\\ 19^{30} &\equiv 2^1 \times 3^1 \times 5^0 \times 7^2&\pmod{337}\\ 19^{36} &\equiv 2^2 \times 3^2 \times 5^0 \times 7^0&\pmod{337}\\ 19^{37} &\equiv 2^1 \times 3^0 \times 5^1 \times 7^0&\pmod{337}\\ &\text{and}\\ 205 \times 19^{-1} &\equiv 2^6 \times 3^0 \times 5^0 \times 7^0&\pmod{337}\\ 205 \times 19^{-5} &\equiv 2^0 \times 3^1 \times 5^2 \times 7^0&\pmod{337}\\ 205 \times 19^{-6} &\equiv 2^1 \times 3^3 \times 5^1 \times 7^0&\pmod{337}\\ \end{align}$$
-
1$\begingroup$ There are books clearly explains the steps An Introduction to Mathematical Cryptography (Undergraduate Texts in Mathematics) and free one Chapter 3 of handbook of applied cryptography page 111, follow the steps. $\endgroup$– kelalakaCommented Apr 22, 2021 at 7:35
-
$\begingroup$ Possible dupe of Incorrect solution for Discrete Log Problem when using the Index Calculus algorithm $\endgroup$– kelalakaCommented Apr 22, 2021 at 7:42
-
$\begingroup$ And please don't cross-post $\endgroup$– kelalakaCommented Apr 22, 2021 at 8:37
1 Answer
The trick is to take logarithms. The information you have above can be translated as $$ \begin{align} 2 &= 3\cdot \log_{19} 2 + 1\cdot \log_{19} 3 + 0\cdot \log_{19} 5 + 0\cdot \log_{19} 7 \pmod{336} \\ 5 &= 5\cdot \log_{19} 2 + 0\cdot \log_{19} 3 + 1\cdot \log_{19} 5 + 0\cdot \log_{19} 7 \pmod{336} \\ & \dots \end{align} $$ This is basically a linear equation system modulo $336$ (the order of $19$ modulo $337$), at the end of which we obtain the logarithms of $2$, $3$, $5$, and $7$ in base $19$, which are $160$, $194$, $213$, and $6$. (This might require solving the system modulo each factor of $336 = 2^4 \cdot 3 \cdot 7$ individually and recombine with the Chinese remainder theorem).
Having those logarithms, we can use one of the other equations to find the logarithm of $205$. For example, $$ 205\cdot 19^{-1} = 2^6 \cdot 3^0 \cdot 5^0 \cdot 7^0 \pmod{337} $$ can again be translated as $$ \log_{19} 205 - 1 = 160\cdot 6 + 194\cdot 0 + 213\cdot 0 + 6\cdot 0 \pmod{336}, $$ from which we easily obtain $\log_{19} 205 = 160\cdot 6 + 1 \bmod 336 = 289$.
