0
$\begingroup$

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?

|improve this question
$\endgroup$
  • 3
    $\begingroup$ Have you looked at the Pohling-Hellman algorithm? Any remaining question after that? $\endgroup$ – fgrieu Jan 23 '19 at 14:59
  • $\begingroup$ You can easily find example. Take a look at this answer for instance. $\endgroup$ – Faulst Jan 25 '19 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.