It is said that for the group $\mathbb{Z}_p^*$, the factorization of $p-1$, is critical.

If $p-1$ has some small factors $q_1, q_2, q_3, q_4$, then when we transmit $g^x \bmod p$ where $g$ is a generator of this group, the attacker can derive $x \bmod q_1q_2q_3q_4$

How does it happen?

Can someone please provide a practical example, say for $p = 29$, where $p$ is prime but $p-1$ has a bunch of small factors?

  • 3
    $\begingroup$ Have you looked at the Pohling-Hellman algorithm? Any remaining question after that? $\endgroup$
    – fgrieu
    Jan 23, 2019 at 14:59
  • $\begingroup$ You can easily find example. Take a look at this answer for instance. $\endgroup$
    – Faulst
    Jan 25, 2019 at 18:15


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.