Cred că am o înțelegere a atacului Pohlig-Hellman asupra curbelor eliptice. De la pagina 31 din Asocieri pentru începători:
- Găsiți ordinea grupului $\#E(\mathbb{F}_q)$, numiți $n$și factorizează-l. Exemplu: $966 = 2 \cdot 3 \cdot 7 \cdot 23$
- Pentru fiecare factor prim $p_i$, mai sus: înmulțiți generatorul $P$ și punctul țintă (nu sunt sigur care este termenul), $Q$, de $n/p_i$ (cofactorul)
- Acest exemplu particular nu are factori primi care sunt ridicați la puteri (de exemplu, factorizarea nu este $2^3 \cdot 5^2$, dar înmulțiți cu $n$ împărțit la primul, nu primul ridicat la exponent)
- Acum avem $[\frac{n}{p_i}]P$ și $[\frac{n}{p_i}]Q$.
- Cunoaștem ordinea $[\frac{n}{p_i}]P$ este $p_i$
- Prin urmare, $[\frac{n}{p_i}]Q = [k \text{ mod } p_i]P$ Unde $kP = Q$
- Rezolvăm pentru $k\text{ mod } p_i$ și repetați pentru fiecare $p_i$
- Apoi, folosind teorema chineză a restului, putem găsi $k\text{ mod } n$
Toate acestea au aproximativ sens. De asemenea, se potrivește cu alte explicații despre Pohlig-Hellman de pe acest site: Algoritmul Pohlig-Hellman.
Cu toate acestea, sunt confuz, deoarece se pare că atacul „complet” Pohlig-Hellman implică reprezentarea $k_i$ la fel de $z_0 + z_1p_i + z_2p_i^2 + ...$
De ce există mai multe variații ale algoritmului Pohlig-Hellman?
