Cum calculăm discriminanții CM fără factoring?

În ECC, există un parametru cunoscut sub numele de discriminatori CM. Să presupunem că urma curbei este $t$ în $Z_p$. Cantitatea de $s^2$ este cea mai mare împărțire a pătratului $t^2-4p$ atunci $\frac{t^2-4p}{s^2}$ este un întreg negativ fără pătrat. Discriminantul CM este $\frac{t^2-4p}{s^2}$ dacă $\frac{t^2-4p}{s^2} \mod 4 = 1$, altfel ca $4(\frac{t^2-4p}{s^2})$. Cum calculăm acest parametru fără factoring? Există vreun algoritm pentru asta? Poate cineva să scrie programul în Sage pentru calcularea D?

Vrem să găsim $D=-n/s^2$ pentru $s^2$ cea mai mare împărțire a pătratului cunoscută $n=4p-t^2>0$ (Unde $t$ este urma si $n$ este de ordinul unei curbe eliptice cu o ecuație în $\mathbb F_p$), pentru același motiv SafeCurves face: constată $-D\ge B$ pentru unii legat $B$ (SafeCurves are $2^{-100}=B$ ). Nu încercasem sau cercetasem niciodată asta. Acest răspuns este o ipoteză sălbatică.

Nu există o metodă cunoscută cu polinom de timp euristic în dimensiunea de $n$ care trage factorii pătrați ai $n$ cu certitudine (sau chiar mare încredere AFAIK), după dorință; și nu am idee despre cineva care lucrează pentru genul de $n$ considerată.

Cel mai bun pe care trebuie să-l propun este încercând a factoriza $n$ folosind metode utilizate pentru numere întregi generale, în special ECM-ul lui Lenstra, diferit de cei (PPMPQS sau GNFS) care ar fi utilizat pentru un module RSA de dimensiunea luată în considerare (în ordinea lui $p$ mai rău); și efectuați un avort timpuriu în cazul relativ rar în care factorizarea completă este greu de obținut.

Metoda (revizuită) pe care o propun este:

1. Trage cât mai mulți factori de $n$ pe cât posibil folosind împărțirea de probă prin numere prime mici și, opțional, puțin rho lui Pollard.

2. În acest moment ne-am exprimat $n$ la fel de $n=u\prod{p_i}^{k_i}$ cu distincte $p_i$, și fiecare $k_i\ge1$. Îmbunătățiți acest lucru (de exemplu, prin diviziunea de probă a $u$ de fiecare $p_i$) astfel încât nu $p_i$ desparte $u$.

3. Dacă $u$ este prim sau $1$, atunci $D=-u\prod{p_i}^{k_i\bmod 2}$, putem testa $-D\ge B$, Stop.

4. Dacă $u$ este un pătrat (care este ușor de testat), atunci $D=-\prod p_i^{k_i\bmod 2}$, putem testa $-D\ge B$, Stop.

5. [opțional] Încercați să scoateți mai mulți factori de $u$ folosind o cantitate limitată de P-1 lui Pollard, și p+1 al lui Williams (ca de exemplu în GMP-ECM); iar dacă aceasta reușește, îmbunătățiți factorizarea și continuați la (2.)

6. În acest moment, știm că unul dintre următoarele două lucruri este valabilă:

   • $u$ este produsul a două numere prime distincte, dintre care niciunul nu este unul de-al nostru $p_i$;
   • $u$ este produsul a trei sau mai mulți factori primi (adică dacă $u=\prod{p_j}^{k_j}$ cu $p_j$ prim atunci $\sum k_j\ge3$ ), prin urmare $u$ este divizibil cu un prim cel mult $\sqrt[3]u$.

   Acum folosim ECM-ul lui Lenstra ca de ex. în GMP-ECM cu speranţa de a găsi un factor mai mic decât $\sqrt[3]u$, sau mai puțin decât limita $B$. Dacă aceasta reușește, îmbunătățiți factorizarea și continuați la (2.)

7. Dacă pasul (6.) nu a descoperit un factor, avem opțiuni:

   • Renunță la efortul nostru pentru această curbă și încearcă una nouă cu speranța că verificarea este mai ușoară;
   • Factor $u$ cu PPMPQS sau GNFS;
   • Ieșire $D=-u\prod{p_i}^{k_i\bmod 2}$ care are doar o probabilitate scăzută să fie incorectă, limitată de probabilitatea calculabilă ca cantitatea de ECM lui Lenstra pe care am făcut-o să nu poată scoate un factor mai mic decât $\sqrt[3]u$
   • Afirma $-D\ge B$ care are doar o probabilitate scăzută să fie incorectă, limitată de probabilitatea calculabilă ca cantitatea de ECM lui Lenstra pe care am făcut-o să nu poată scoate un factor mai mic decât $B$