# Why are there different versions of the Pohlig-Hellman attack?

I think I have an understanding of the Pohlig-Hellman attack on elliptic curves. From page 31 of Pairings for Beginners:

• Find the group order $$\#E(\mathbb{F}_q)$$, call it $$n$$, and factor it. Example: $$966 = 2 \cdot 3 \cdot 7 \cdot 23$$
• For each prime factor $$p_i$$, above: multiply the generator $$P$$ and target point (not sure what the term is), $$Q$$, by $$n/p_i$$ (the cofactor)
• This particular example does not have any prime factors that are raised to powers, (e.g the factorization is not $$2^3 \cdot 5^2$$, but you multiply by the $$n$$ divided by the prime, not the prime raised to exponent)
• Now we have $$[\frac{n}{p_i}]P$$ and $$[\frac{n}{p_i}]Q$$.
• We know the order of $$[\frac{n}{p_i}]P$$ is $$p_i$$
• Thus, $$[\frac{n}{p_i}]Q = [k \text{ mod } p_i]P$$ where $$kP = Q$$
• We solve for $$k\text{ mod } p_i$$ and repeat for each $$p_i$$
• Then, using Chinese Remainder Theorem, we can find $$k\text{ mod } n$$

This all roughly makes sense. It also matches up with other explanations of Pohlig-Hellman on this site: Pohlig-Hellman algorithm.

However, I'm confused b/c it seems like the "full" Pohlig-Hellman attack, involves representing $$k_i$$ as $$z_0 + z_1p_i + z_2p_i^2 + ...$$

Why are there multiple variations of the Pohlig-Hellman algorithim?

Actually, the method using the Chinese Remainder Theorem is the more general version. The one representing $$k_i$$ as $$z_0 + z_1p_i + z_2p_i^2 + ...$$ is only useful in the situation that the group order is a prime power (a power of $$p_i$$), so you solve in each of the smaller powers first and build up. You use the CRT (or a mixture of both) when the groups are not all powers of the same prime. In both cases, the idea is the same - solve the DLP in a smaller subgroup and use that information to reconstruct the solution in the full group.
• To clarify, when you say the "group order" you mean the order of the sub-group $p_i^{n_i}$ right? Jan 28, 2022 at 16:13