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$
2
  • 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

0

Reset to default

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.