Unable to understand the final step in Pohlig-Hellman algorithm to solve the Discrete Log Problem

127 Views Asked by At

To solve for $x$

$2^x \equiv 41 \mod 211$

$\phi(p) = p - 1 = 210 = 2.3.5.7$

Solving by Pohlig-Hellman, we get to

$x \equiv 3 \mod 7$
$x \equiv 2 \mod 5$
$x \equiv 2 \mod 3$
$x \equiv 1 \mod 2$

Then using Chinese Remainder theorem we get

$x \equiv 17 \mod 210$

I understood everything up to the above step.

But 17 is the value of $x$ for modulo 210. How do we go from here to $2^{17} \equiv 41 \mod 211$?

What is the relation between $x$ for modulo 210 & the $2^x$ in modulo 211? We already knew $x$ for 2, 3, 5 & 7. Why don't any of those values work as x for $2^x$ for modulo 211?

1

There are 1 best solutions below

0
On BEST ANSWER

$2^{x\equiv 17\bmod 210}=2^{17}\times (2^{210})^k$

$ 2^{210}\equiv 1 \bmod 211$

$2^x\equiv 2^{17} \bmod 211\equiv 41\bmod 211$