Puncte:0

De ce există versiuni diferite ale atacului Pohlig-Hellman?

drapel fr

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?

Puncte:2
drapel gb

De fapt, metoda care utilizează teorema chineză a restului este versiunea mai generală. Cel care reprezintă $k_i$ la fel de $z_0 + z_1p_i + z_2p_i^2 + ...$ este utilă numai în situația în care ordinea grupului este o putere primă (o putere a $p_i$), așa că rezolvi în fiecare dintre puterile mai mici mai întâi și construiești. Folosiți CRT (sau un amestec al ambelor) atunci când grupurile nu sunt toate puteri ale aceluiași prim. În ambele cazuri, ideea este aceeași - rezolvați DLP într-un subgrup mai mic și utilizați acele informații pentru a reconstrui soluția în întregul grup.

Foobar avatar
drapel fr
Pentru a clarifica, când spui „ordinea grupului” te referi la ordinea subgrupului $p_i^{n_i}$ nu?
meshcollider avatar
drapel gb
Ordinea completă a grupului în care calculați conectarea discretă. În exemplul din întrebarea dvs., ordinea a fost compusă (966), așa că folosim CRT. Dacă ordinea ar fi, să zicem, 3^5, am folosi mai întâi subgrupul de ordine 3, apoi 3^2, apoi 3^3 etc.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.