Score:1

Recovering alternate solutions to a discrete logarithm that can be attacked using Pohlig-Hellman

in flag

In the process of studying discrete logarithms and approaches that could be taken, I saw the Pohlig-Hellman algorithm.

Later when I was working with $h = g^x \mod p$ where $p-1$ is smooth, using Pohlig-Hellman did not give the expected result, and returned something much larger than expected. I assume this is because Pohlig-Hellman skips over the smallest answer occasionally.

Questions:

  1. How can I recover the smallest possible $x$ correctly?
  2. I have the larger $x$; could that be used to recover a smaller $x'$?
kelalaka avatar
in flag
Did you see [Pohlig–Hellman algorithm : General algorithm](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm#The_general_algorithm)
in flag
@kelalaka I read through that. It looks like the general how-to-use the algorithm. I dont see how that allows for alternate solutions however. Can you point me towards what Im supposed to look at?
meshcollider avatar
gb flag
The smallest would be $x \bmod{(p-1)}$ if $p$ is prime
et flag
All the solutions are part of an equivalence class given by $\bmod (p-1)$. So $x' = x \bmod (p-1)$. That said, the final step in the PH algo is to combine solutions in subgroups using the Chinese Remainder Theorem & the solution would be in the form $x = something \bmod (p-1)$. So you will always end up with the smallest solution. Could you list your different subgroup solutions which you combine with the CRT?
in flag
@user93353 I ended up solving it from your message. Thanks!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.