Join Log in
Score:1
avatar Crypto

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

in flag
ARandomUser

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'$?
59
0 + 0
kelalaka avatar
in flag
kelalaka
Did you see [Pohlig–Hellman algorithm : General algorithm](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm#The_general_algorithm)
0
Reply
in flag
ARandomUser
@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?
0
Reply
meshcollider avatar
gb flag
meshcollider
The smallest would be $x \bmod{(p-1)}$ if $p$ is prime
0
Reply
et flag
user93353
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?
0
Reply
in flag
ARandomUser
@user93353 I ended up solving it from your message. Thanks!
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.