# Combining Hellman Pohlig with Sieve

Suppose integer $m$ has $\phi(m)=2pq^5r^2$ where $p,q,r$ are primes.

Hellman-Pohlig says that finding discrete log $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ suffices to find $z\bmod\phi(m)$ in $g^z=h\bmod m$.

It could be that $p,q^5,r^2$ are still very large and there is a Big-step-small-step which is still exponential.

Can we apply sieve techniques to each of $z\bmod p$, $z\bmod q^5$, $z\bmod r^2$ and $z\bmod 2$ cases separately?

• @poncho I am also looking at case of $m=2q+1$ where $q=r=1$ (like safe prime) but still I don't follow your comment. – 1.. Nov 1 '16 at 19:59
• Sorry, I was thinking in the context of factoring, not discrete logs... – poncho Nov 1 '16 at 20:01

## 1 Answer

I'm not sure if I understand the question correctly, but let's try anyway.

By assumption we have some integer $m$ such that $\varphi(m)=2pq^5r^2$ for primes $p,q,r$. The goal is to solve a discrete logarithm problem in $\mathbb{Z}_m^*$, say we have $g,h\in\mathbb{Z}_m^*$ such that $h=g^\ell$ for some integer $\ell$.

We note that $\mathbb{Z}_m^*$ is a finite abelian group of order $\varphi(m)$, so by the fundamental theorem of finite abelian groups we have that $\mathbb{Z}_m^*\cong\mathbb{Z}_2\times\mathbb{Z}_p\times G(q^5)\times G(r^2)$, where $G(q^5)$ and $G(r^2)$ are groups of order $q^5$ and $r^2$ respectively (they are Sylow subgroups). Pohlig-Hellman implicitly makes use of this fact. That is, instead of finding $\ell\pmod{\varphi(m)}$ directly, we map $g$ and $h$ to elements of $\mathbb{Z}_2$, $\mathbb{Z}_p$, $G(q^5)$ and $G(r^2)$ respectively. We then solve the DL's in those groups, finding $\ell\pmod{2}$, $\ell\pmod{p}$, $\ell\pmod{q^5}$ and $\ell\pmod{r^2}$. Finally we recombine them using the Chinese Remainder Theorem.

For example, since $g$ and $h$ have order dividing $\varphi(m)$, we have $g^{2pq^5r^2}\equiv h^{2pq^5r^2}\equiv 1\pmod{m}$. That means that $(g^{pq^5r^2})^2\equiv (h^{pq^5r^2})^2\equiv 1\pmod{m}$, i.e. they are both elements of order 2. In other words, we can think of them as lying in $\mathbb{Z}_2$. Thus, we have that $h^{pq^5r^2}=(g^{pq^5r^2})^{\ell\pmod{2}}$. This is an easy DL and we solve it to find $\ell\pmod{2}$.

So we have reduced to solving DL's in $\mathbb{Z}_2$, $\mathbb{Z}_p$, $G(q^5)$ and $G(r^2)$. Carefully looking at the Pohlig-Hellman shows that we can actually reduce the DL in $G(q^5)$ to 5 DL's in $\mathbb{Z}_q$. Similarly we reduce the DL in $G(r^2)$ to 2 DL's in $\mathbb{Z}_r$. Hence the remaining problem is solving some DL's in the group $\mathbb{Z}_s$, for $s\in\left\{2,p,q,r\right\}$. That is, a prime order cyclic group.

You may start wondering why I'm going through all of this. The point is that the usefulness of Pohlig-Hellman is precisely this reduction step. Assuming that $p,q,r$ are all small, we can easily solve all DL's in our groups $\mathbb{Z}_s$. However, what if $p,q,r$ are not small? Then we have to solve the DL's in $\mathbb{Z}_s$ some different way, but Pohlig-Hellman does not come with any restrictions. The most straightforward way would perhaps be Baby-Step Giant-Step, but we are free to choose any other method.

Therefore in relation to your actual question, any sieving technique that applies to solving a DL in a prime order group, will also apply here. Although I guess it is most commonly known for factoring, there are definitely applications of the NFS to these groups, see e.g. https://cr.yp.to/bib/2003/joux.pdf.

• You misunderstand what the structure theorem for finitely generated abelian group says. Your isomorphism statement is correct if and only if the group is cyclic. – fkraiem Nov 6 '16 at 11:30
• I am not stating the structure theorem for "finitely generated" abelian groups but "finite" abelian groups. There are many references, for example math.hmc.edu/~omar/math171F14/m171.notes.11.03.pdf. Alternatively we only need that a finite abelian group is isomorphic to the direct product of its Sylow subgroups. – CurveEnthusiast Nov 6 '16 at 11:47
• You can nitpick all you want, the fact is that you are stating an isomorphism without justification. – fkraiem Nov 6 '16 at 11:59
• Looks like you are just repeating what's in this document without understanding it. – fkraiem Nov 6 '16 at 12:02
• I'm sorry, I don't understand your attitude here. First of all this isomorphism is not the core of the problem, so it would probably be counterproductive to spend too many words on it. You question the correctness, and when I answer your question you tell me I am nitpicking. Furthermore I don't see how you can be in a position to question my understanding of the material. To bring this back to a useful discussion, which you seem to attempt to avoid at all cost, do you think the isomorphism is correct or not? – CurveEnthusiast Nov 6 '16 at 12:10