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

Question

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?

Answer 1

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.