Use the Pohlig-Hellman algorithm to compute a solution to:
$3^x\equiv 2 \pmod {65537}$

My attempt:

$p-1 = 65537-1 = 65536= 2^{16}$
$x= 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$
For $x_0$:
$1 \pmod {65537} \equiv (-1)^{x_0} \pmod{65537}$
So $x_0 = 0$
Is this right? Because for all other steps after that, I get $0$'s for all $x_i$'s where $i=1,2,3,...,15$

Any help would be appreciated!

  • $\begingroup$ Probably you have an error in your computations for the higher $i$. The first step seems to be fine. $\endgroup$ – tylo Feb 24 '15 at 10:13

You are correct in the procedure. You need to express $x$ as $x = 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$
Where the $x_i$ are in $GF(2)$

First compute:
$3^{(0*(p-1)/2)} \pmod p \equiv 1$
$3^{(1*(p-1)/2)} \pmod p \equiv 65536$

So that when you'll compute $2^{65536/2^{i+1}} \pmod p$ you'll get either 1 (corresponding to $x_{i} = 0$) or 65536 (corresponding to $x_{i} = 1$)

For the first values of $i$ you will get only $x_i=0$, but then for $i=11$: $2^{65536/2^{12}} \pmod p\equiv 65536$ which corresponds to $x_{11}=1$

Then you need to proceed... but I just wanted to show that you don't get 0 for all $x_i$

| improve this answer | |

In binary representation, your dlog has quite a few $0$s in the least significant bits, so quite a few $x_i$ are 0. But if you have the transition to the next step correctly, it will change at some point.

| improve this answer | |

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.