Semnificația câmpului factorului în ECM lui Lenstra

Citatul invită la calcul $5\,P$ pe curba eliptică a ecuației $E:\ Y^2\equiv X^3+3X+7\pmod{11}$ pentru a ajunge experimental la realizarea acesta este punctul de la infinit $\mathcal O$ (neutrul adunării punctelor) și obțineți intuiția, de aceea calculul $5\,P$ pe curba eliptică a ecuației $E:\ Y^2\equiv X^3+3X+7\pmod{187}$ (după cum este realizat de algoritm) dă o valoare care nu poate fi inversată modulo $187$.

Toate acestea provin din Teorema restului chineză. Posibile afirmații și consecințe ale acesteia sunt: ​​pentru $n=p\,q$ cu $\gcd(p,q)=1$ (inclusiv $n=187$ , $p=11$ , $q=17$ ca in exemplu)

• Orice cantitate modulo $n$ poate fi calculat în mod echivalent modulo $p$ și modulo $q$.
• The inel de numere întregi modulo $n$, remarcat $\mathbb Z_n$, are un izomorfism canonic cu $\mathbb Z_p\times\mathbb Z_q$.
• Pentru orice număr întreg $z$ în $[0,n)$ putem defini în mod unic $z_p=z\bmod p$ și $z_q=z\bmod q$, și apoi ține $z=\left((q^{-1}\bmod p)\,(z_p-z_q)\bmod p\right)\,q+z_q$.
• Pentru o curbă eliptică dată de ecuație luată modulo $n$, și puncte $U$ și $V$ pe acea curbă, dacă putem calcula $U+V$ conform ecuațiilor de adunare a punctelor unei curbe eliptice într-un câmp, cedând $(X,Y)$ ; atunci putem face același lucru în mod echivalent pentru curbele cu aceeași ecuație luată modulo $p$ și modulo $q$ coordonate ce decurg $(X_p,Y_p)$ și $(X_q,Y_q)$ , apoi obțineți $(X,Y)$ prin aplicarea de două ori a metodei din punctul de mai sus.
• Cele de mai sus pentru adunarea punctelor se extind la înmulțirea punctelor cu un număr întreg.

Ce perspectivă ne oferă acest lucru?

Obținem această perspectivă calculând pe o curbă eliptică în ring $\mathbb Z_n$ pentru $n$ de factorizare (inițial) necunoscută ca și cum ar fi un câmp (nu este), am reușit să calculăm și pe o curbă eliptică în inel $\mathbb Z_p$ Unde $p$ este un factor (inițial) necunoscut al $n$. Și (încă fără o dovadă formală, dar cu un exemplu lămuritor) motivul pentru care calculul pe o curbă în $\mathbb Z_n$ a lovit un invers necalculabil este că punctul de la infinit $\mathcal O$ a fost atins pe curba într-una din $\mathbb Z_p$ sau $\mathbb Z_q$ (presupunând $p$ și $q$ sunt prime, fac $\mathbb Z_p$ și $\mathbb Z_p$ câmpuri, și $\mathcal O$ pe curba corespunzătoare bine definită).

Asta ne lasa sa intelegem De ce algoritmul funcționează, ceea ce, la rândul său, permite să raționăm despre el și să evalueze probabilitatea de succes (adică de a descoperi un factor non-trivial de $n$). Când $n$ este produsul unor numere prime distincte $p_i$, acea probabilitate este suma probabilităților ca punctul de la infinit să fie atins pentru una din curbele pentru fiecare dintre $p_j$, minus probabilitatea (foarte mică) ca acesta să fie lovit simultan pe toate curbele.