Când este posibil de factorizat un semiprim mare?

În ce condiții este posibil de factorizat un semiprim mare? În special, următorul semiprim de 400 de cifre este de fapt trivial pentru a descompune în numere prime?

6962155154859963260211100482357357666900094513013513488352858667799199787495340476167566639530574848375895722792291996203873323650274512138128403360943634134259376986501375967452208380337012919869885380406071772232795575963202558402893589313281327208179913789760736615950818685956393838601277519011418885197723428318400763080858914698836058070301404903262955501113318317950597435778777212408626799143

„Trivial” este aproape sigur cuvântul greșit pentru asta. O întrebare mai bună este dacă este rezonabil să factorăm eficient. În primul rând, merită menționat că semiprimul tău este 400 zecimal cifre. Înmulțind acest lucru cu $\log_2(10)$, vedem că este $\aproximativ 1300$ biți lungi. Aceasta este cu mult mai mare decât cea mai mare înregistrare de factoring (a semiprimelor) revendicată 829 de biți. Deci răspunsul este „nu”, cu excepția cazului în care semiprimul tău are o structură specială care îl face „slab”.

Ce structură specială ar putea avea semiprimele? Lăsa $N = p_1p_2$ fie factorizarea. Sunt câțiva candidați, care funcționează dacă

1. Unul dintre $p_i$ este mic (spun cel mult $\aproximativ 60$ biți), apoi metoda curbei eliptice este rezonabil de rulat.

2. Unul dintre $p_i$ este astfel încât $p_i+1$ este neted, de exemplu. toți factorii primi ai $p_i+1$ sunt delimitate de un număr rezonabil de mic $B$. Atunci a lui William $p+1$ algoritmul este rezonabil.

3. Unul dintre $p_i$ este astfel încât $p_i-1$ este powersmooth, de exemplu. toate prime putere factori ai $p_i-1$ sunt delimitate de un număr rezonabil de mic $B$. Atunci a lui Pollard $p-1$ algoritm este rezonabil.

Pot exista alte câteva „structuri speciale” care îmi lipsesc (se pare că îmi amintesc una dacă $p_1\aproximativ p_2$, dar nu-mi amintesc numele acum). Singura dvs. șansă reală de factorizare a numărului este ca acesta să fie generat incorect, totuși, din care toate cele de mai sus ar fi exemple, așa că, dacă nu aveți un motiv anume să credeți că sunt generate incorect (să spunem că aceasta este o provocare CTF) nu te obosi să încerci să-l spargi.

Dacă aveți un motiv să credeți că acest lucru ar trebui generat incorect, există implementări ale acestora. De exemplu, Salvie are o implementare a ECM (prin GMP-ECM). În GMP-ECM pagina în sine, văd și referințe la $p-1$ și $p+1$, dar nu știu dacă sage le încearcă direct și pe acestea (deoarece sunt cu adevărat utile doar dacă bănuiți că semiprimele au fost generate incorect).

Dar fără a atinge unul dintre aceste cazuri de „semiprime slabe” (care este extrem de puțin probabil să apară dacă semiprimul este generat corect --- deci dacă nu aveți motive să credeți că acesta este un slab RSA semiprime probabil nici nu merită verificat).

Într-un comentariu, @Sam Blake a pus o întrebare ulterioară despre un număr întreg de factor:

7215955072690155355400859323297730634528493510676300043022948136348249037517276095868127042993906604904230826475281383188764473510881994780947137238252071087749294743150564851420395422525735221770067605216401023

Întrebarea este că acest al doilea semiprim este de fapt trivial de factor în numere prime?

Acest semiprim nu este slab pentru că nu renunță foarte ușor la forma sa specială.

Este slab pentru un adversar cu capacitate de stat național, deoarece are doar 701 de biți. Se recomandă un modul de 2048 biți sau mai mare cu lungimea de biți egală p și q.

De asemenea, nu pare să aibă slăbiciune folosind Fermat, p-1, raportul nu este aproape mic. fracție, ECM nu este de ajutor.

Acest număr întreg nu pare să se potrivească cu o formă specială care este ușor de factorizat. Chiar dacă odată ce forma specială este recunoscută, numărul poate fi factorizat cu mult mai puțin efort, detectarea formei speciale poate fi foarte consumatoare de timp, deoarece există multe forme.

Ce indicii ești dispus să dai? Că acesta este un semiprim? Că factorii sunt de lungime inegală? Că factorii sunt polinoame cu termeni: a0 x 2^(k0) + a1 x 2^(k1) + a2 x 2^(k2)...

Tehnica folosită a fost reducerea N la o formă specială care a fost ușor de factorizat.

Afișat N în binar și observat sute de 0 între 4 numere.

Aceasta a fost redusă la următoarele:

N = a2^1228+b2^875+c*2^353+d

Unde a= 1506291488774150974626762365373 b= 322571915263178581 c= 576377099039115423 d= 123431

Tratând acest lucru ca un polinom în x, cu x=2:

N = ax^1228+bx^875+c*x^353+d

Acest lucru determină foarte repede:

(359561509069941x^353+77)(4189245652768553*x^875 + 1603)