4
$\begingroup$

I want to solve this discrete logarithm problem with Pohlig–Hellman algorithm:

$$2^{x} \equiv{ 2070442609353644988500364779751625112994538364565830646055667805\\ 1945605813418120257083690993568845753318608515495923060805120997\\ 3428789429908548559535354422962118802026940584074383162419987316\\ 4251257235243687584403222687359220263252625476372842589113471426\\ 1782004893903634453733275871450024554309850603821543260259554681\\ 9788249500416881166827892874757890895573842787278113899169213463\\ 6207754656894365789382736647587424234413487070250150001802765877\\ 5362018623752370739226509} \pmod {6561}$$

In fact, I don't know how to do it, because the numbers look terrible. For to solve this discrete logarithm I've read a few examples in PDF books. But, I couldn't apply this problem. It doesn't seem like the problem I can solve on one's own. I hope you can help.

Thank you very much!

$\endgroup$
  • 1
    $\begingroup$ $2$ isn't terrible. $6561$ isn't terrible. And since it's modulo $6561$, the other number simplifies to $2054$ (done by Maple in negligible time). $\endgroup$ – David Feb 4 '19 at 22:39
  • 5
    $\begingroup$ To reduce that monster mod $6561$? Note that $6561 = 9^4$. Divide by $9$ four times (doable by hand), noting the remainders. It takes some time and a lot of space on the scratch paper, but it's not hopelessly complicated. $\endgroup$ – jmerry Feb 4 '19 at 23:11
  • 1
    $\begingroup$ I can't believe you are expected to do that by hand... $\endgroup$ – TonyK Feb 5 '19 at 0:40
  • 1
    $\begingroup$ Here is a worked example I did - math.stackexchange.com/questions/2514365/…. Can you try that and see if you can follow it? $\endgroup$ – Moo Feb 5 '19 at 6:05
  • 1
    $\begingroup$ The Euler $\phi$ of $3^8$ is $\phi(3^8)=2\cdot3^7=4374$. Meaning that the discrete logarithm takes values in the group $\Bbb{Z}_{4374}$. Not in $\Bbb{Z}_{6560}$ as you seem to think. $\endgroup$ – Jyrki Lahtonen Feb 6 '19 at 23:04
1
+50
$\begingroup$

I aborted trying to reduce that monster mod 6561 by hand, but I'll still go through with the algorithm by hand.

First, because everything that matters is mod powers of $3$, we'll do our arithmetic base 9. We wish to solve $2^x\equiv 2732_9\mod 10000_9$.

The first step of the algorithm is to split things up based on the prime factors of the order of the group we're working in. Here, that order is $n=\phi(3^8)=2\cdot 3^7$.

First, powers of $2$. Raise both the generator and the objective to the $\frac{n}{2}$ power; we wish to solve $\left(2^{3^7}\right)^x\equiv(2732_9)^{3^7}$ - or, simply, $(-1)^x\equiv-1$. (We only need to know what $k$ is mod $3$ to determine its $3^7$ power mod $3^8$). The solution is $x\equiv 1\mod 2$.

Next, powers of $3$ - the interesting part. Raise both generator $g$ and objective $h$ to the $\frac{n}{3^7}=2$ power: $2^2\equiv 4$ and $$2732_9^2 = \begin{array}{r}5564\phantom{000}\\ 21645\phantom{00}\\ 8406\phantom{0}\\5564\\ \hline 7840234\end{array}\equiv 0234_9$$ Now we get down to the prime-power algorithm, solving $4^x\equiv 0234_9\mod 10000_9$ (in the order $3^7$ subgroup). First, we need to compute $\gamma \equiv 4^{3^6}$. $(1+3)^{3^6}=1+3\cdot 3^6+3^2\cdot \binom{3^6}{2}+3^3\cdot\binom{3^6}{3}+\cdots$ and all but the first two terms are divisible by $3^8$, so $\gamma = 4^{3^6}\equiv 3001_9\mod 10000_9$.

Now, the core loop. We run $k$ from $0$ to $6$, first computing $h_k=\left(g^{-x_k}h\right)^{3^{6-k}}$, then finding $d_k$ such that $\gamma^{d_k}=h_k$, then setting $x_{k+1}=x_k+3^k d_k$.

While the wiki page I copied the algorithm suggests the "baby-step giant-step" algorithm for finding $d_k$, we won't do that here - $d_k$ ranges from $0$ to $p-1$, and for $p=3$ we can find it by inspection.

$k=0$:
$x_0$ is initialized as zero, of course. We have $h_0\equiv (0234_9)^{3^6} \equiv 4+(3^2\cdot 23_9)^{3^6} \equiv 4^{3^6}+3^8\cdot\text{stuff}\equiv 3001_9$.
Then $3001_9^1\equiv 3001_9$ and $d_0=1$.
Finally, $x_1= 0 + 1\cdot 1 = 1$.

$k=1$:
$h_1\equiv (4^{-1}\cdot 0234_9)^{3^5}\equiv (6731_9)^{3^5}\equiv (1+3^3\cdot\text{stuff})^{3^5}\equiv 1$.
This makes $d_1=0$.
Finally, $x_2=1+3\cdot 0=1$.

$k=2$:
$h_2\equiv (4^{-1}\cdot 0234_9)^{3^4}\equiv (6731_9)^{3^4}\equiv (1+3^3\cdot(1+3\cdot \text{stuff}))^{3^4}\equiv 1 +3^7\cdot(1+3\cdot \text{stuff})\equiv 3001_9$.
This makes $d_2=1$.
Finally, $x_3=1+3^2\cdot 1=11_9$.

$k=3$:
$h_3\equiv (4^{-11_9}\cdot 0234_9)^{3^3}$. This takes some calculation, but $4^9\equiv 8531_9$ and $4^{-9}\equiv 4361_9$. Then $4361_9\cdot 6731_9\equiv 1\color{red}{2}01$. Now $h_3\equiv (1201_9)^{3^3}\equiv \left(1+3^4(2+3^2)\right)^{3^3}\equiv 1+2\cdot 3^7+\text{stuff}\equiv 6001_9$.
This makes $d_3=2$.
Finally, $x_4=11_9+3^3\cdot 2=71_9$.

$k=4$:
$h_4\equiv (4^{-71_9}\cdot 0234_9)^{3^2}\equiv \left(4^{-2\cdot 3^3}\cdot 1201_9\right)^{3^2}$. We have $4^{3^3}\equiv 1701_9$ and $4^{-3^3}\equiv 7201_9$; square and multiply by $1201_9$ for $(1200_9+7200_9+7200_9)+1\equiv 6601_9$. Now $h_4\equiv (6601_9)^{3^2}\equiv 6001_9$.
This makes $d_4=2$.
Finally, $x_5=71_9+3^4\cdot 2=271_9$.

$k=5$:
$h_5\equiv (4^{-271_9}\cdot 0234_9)^3\equiv \left(4^{-2\cdot 3^4}\cdot 6601_9\right)^3$. We have $4^{3^4}\equiv 1701_9^3\equiv 1+3\cdot 1701_9\equiv 5301_9$ and $4^{-3^4}\equiv 3601_9$; square and multiply by $6601_9$ for $5001_9$. Now $h_5\equiv (5001_9)^3\equiv 6001$.
This makes $d_5=2$.
Finally, $x_6=271_9+3^5\cdot 2=871_9$.

$k=6$:
$h_6\equiv (4^{-871_9}\cdot 0234_9)^1\equiv \left(4^{-2\cdot 3^5}\cdot 5001_9\right)^1$. We have $4^{-3^5}\equiv 2001$; squaring and multiplying gives $h_6\equiv 1$.
This makes $d_6=0$.
Finally, $x_7=871_9+3^6\cdot 0=871_9$.

That's our result: $x\equiv 871_9\mod 3^7$. Converting back to base ten, that's $x\equiv 8\cdot 81+7\cdot 9+1\equiv 712\mod 2187$.

The final step is to combine what we got for powers of 2 and powers of 3. We want something that's $1$ mod $2$ and $712$ mod $2187$; final answer $2899\mod 4374$.

My first-run answer doesn't match. Time to check it... Spreadsheet-aided checking found the error, marked in red (1101 by initial calculation, leading to $3025$ final answer). Recalculating from there forward... OK, got it now.

While the work involved in doing this by hand isn't too hard, it's so long that it's really easy to make an arithmetic mistake leading to a wrong answer. I wouldn't recommend it without at least machine-checking the various arithmetic pieces. No particularly sophisticated tools are needed for that, at least.

$\endgroup$
  • $\begingroup$ You really did a hard work. Is this Pohlig hellman algorithm? $\endgroup$ – Elementary Feb 11 '19 at 7:29
  • $\begingroup$ I have $2$ question to You ..If $d_1,d_2,d_3,d_4,d_5,d_6$ are known, can we direct solve the this discret log? And are the values ​​you find for $ d_1,d_2,d_3,d_4,d_5,d_6$ are definitely correct? Thank you very much. $\endgroup$ – Elementary Feb 11 '19 at 7:43
  • 1
    $\begingroup$ I copied it from the very link in your question. It's the Pohlig-Hellman algorithm. As for the $d_i$, their values directly give us the discrete logarithm (in the prime-power case). It's just that they're not going to come up independently of running the algorithm. The answer? It matches that found by someone putting the numbers into an online implementation. It's right. $\endgroup$ – jmerry Feb 11 '19 at 7:49
  • $\begingroup$ Sorry for the bad questions. I don't know the subject.Only specifically, for $2^x\equiv 2054 \pmod {6561}$ if $d_1,d_2 \cdots d_6$ is known, can we find the smallest $x$ (discrete logarithm) directly? $\endgroup$ – Elementary Feb 11 '19 at 8:10
  • $\begingroup$ It's not the whole problem - the $d_i$ get us the exponent mod $3^7$. We also need to know the exponent mod $2$. $\endgroup$ – jmerry Feb 11 '19 at 8:14
1
$\begingroup$

They have whittled it down to a very tractable problem in the comments.

I tried to solve the dl problem $2^x\cong 2054\pmod{6561}$ using the Pohlig-Hellman algorithm, but didn't quite manage to do it by hand.

I ran into a problem, I don't know if it's a bug or (probably) just me.

Anyway I found a calculator online that spat out the answer in a matter of seconds.

It gave

$2899+4374k$.

$\endgroup$
  • $\begingroup$ alpertron.com.ar/DILOG.HTM :) $\endgroup$ – Elementary Feb 10 '19 at 8:21
  • $\begingroup$ Ok. So you're well aware of it. The problem I ran into was $d_k\in\{0,1,2\}$ did not seem to be unique. It seemed it could be $0$ or $2$, since $\gamma\cong6560\cong -1\pmod {6561}$. $\endgroup$ – Chris Custer Feb 10 '19 at 8:42
  • $\begingroup$ (+1)Thank you for your time and for your help. please do not delete your answer. $\endgroup$ – Elementary Feb 10 '19 at 9:02
  • $\begingroup$ Can you explain me what is $d_k$? Thank you very much. $\endgroup$ – Elementary Feb 10 '19 at 11:09
  • $\begingroup$ Sure. I was doing the Pohlig-Hellman algorithm in the case where $G$ has prime power order: $6561=3^8$. It's in step $2$ of part $3$ of the algorithm. Use the link you included. $\endgroup$ – Chris Custer Feb 10 '19 at 12:43

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.