Let's try to solve a discrete logarithm:

$\beta \equiv \alpha ^{x} \bmod \,\, p$

using the Pohlig-Hellman algorithm. Let's suppose that $p-1=tq$, where $q$ is a large prime number. This means that the resolution is probable infeasible, however, if $t$ is factorizable with small prime numbers the algorithm can determine the discrete logs $\bmod t$ in an efficient way. But at this point, what i do with the discrete logs $\bmod t$?

I am also having trouble understanding this passage:

Note that even if $p - 1 = tq$ has a large prime factor $q$, the algorithm can determine discrete logs mod $t$ if $t$ is composed of small prime factors. For this reason, often $\beta$ is chosen to be a power of $\alpha^t$. Then the discrete log is automatically $0$ mod $t$, so the discrete log hides only mod $q$ information, which the algorithm cannot find. If the discrete log $x$ represents a secret (or better, $t$ times a secret), this means that an attacker does not obtain partial information by determining $x \bmod t$, since there is no information hidden this way. This idea is used in the Digital Signature Algorithm, which we discuss in Chapter 9.

enter image description here


The point is that even though $p - 1 = tq$ may be large, the discrete log security of $(\mathbb Z/p\mathbb Z)^\times$ against Pohlig–Hellman depends on the size of $q$, not on the (possibly much larger) size of $p$ or $tq$. If $q$ is the largest prime factor, then the cost of computing discrete logs modulo $p$ is essentially at most the cost of computing order-$q$ discrete logs in Pohlig–Hellman. This is why, e.g., Schnorr groups are chosen to have an order with a large prime factor.

  • $\begingroup$ Thanks so much, I show you what i haven't understood, directly from the book imgur.com/a/XTxoWZc Can you explain me ? $\endgroup$ – AleWolf Nov 15 '19 at 20:58
  • $\begingroup$ @AleQuercia imgur.com is not working. Can you please typeset it, or at least include it in your question as an inline image? $\endgroup$ – Squeamish Ossifrage Nov 15 '19 at 21:15
  • $\begingroup$ I added the picture in the main post $\endgroup$ – AleWolf Nov 16 '19 at 11:31

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.