Does Pohlig-Hellman algorithm work for non-prime powers?

nickponline

11/30/23, 8:50 PM

I implemented the Pohlig-Hellman algorithm for the general case following Wikipedia but it only seem to work for prime powers (which is what the limited case is meant to solve).

My implementation follows wikipedia exactly: https://gist.github.com/nickponline/2ef6f3456ed6c423239a334c98728324

Some examples where it fails to find a solution are:

39^x = 49 (mod 74) x = 28
19^x = 423 (mod 478) x = 275
71^x = 65 (mod 86) x = 45

I'm unclear why my implementation doesn't work for p where p is not a prime power.

0 + 2

discrete-logarithm

pohlig-hellman

Daniel S

11/30/23, 9:18 PM

You are treating the modulus of the multiplicative group ($p$ in your notation) as the order of the multiplicative group. This will not be the case in general. For a prime power $p=q^r$, elements will generally have order $q^{r-1}(q-1)$ and recovering the discrete logarithm mod $q^{r-1}$ may suffice. For general moduli, the best that we can say is that the order of $g$ divides $\lambda(p)$ where $\lambda$ is the [Carmichael function](https://en.wikipedia.org/wiki/Carmichael_function).

nickponline

12/1/23, 3:18 AM

Thank you that was indeed the issue.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does Pohlig-Hellman algorithm work for non-prime powers?

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.