Câtă muncă să găsești astfel de $n$?

Lăsa $W$ fii aleatoriu $200$ număr de biți. Câtă muncă ar fi nevoie pentru a găsi un semiprim $n=p_1\cdot p_2$ astfel încât $p_1,p_2 > 2^{50} $ și $|W-n|<2^{12}$?

Mai general, lasă $W_b$ fie un număr întreg aleatoriu cu $b$ biți. Câtă muncă ar fi nevoie pentru a găsi un semiprim $n=p_1\cdot p_2$ astfel încât $p_1,p_2 > \sqrt[4]{W_b} $ și $|W_b-n|<\sqrt[8]{W_b}$?

Cea mai bună metodă de a găsi astfel de numere pe care le cunosc ar fi algoritmul 3 din lucrarea lui Marc Joye Moduli RSA cu o porțiune predeterminată: tehnici și aplicații. În acest caz, luând $n=200$, $n_0=150$ și $\kappa'=188$. Cerințele inițiale ale problemei sunt agresive și este foarte posibil să existe valori de 200 de biți ale $W$ pentru care nu există semiprim potrivit în acel interval.Investigația lui Joye a examinat complexitatea metodei doar într-o manieră experimentală. Voi citi și voi încerca să vin cu o euristică.

Este simplu să descrii și să analizezi euristic metoda „folclorică” de a alege un 50 de biți $p$, setare $q_0=\lceil W/p\rceil$ și testare $q_0$ pentru primalitate. Ar trebui să fie nevoie de aproximativ 105 de opțiuni diferite $p$ pentru a găsi un prim $q$ de 150 de biți. Pentru această pereche primii 150 de biți se vor potrivi $W$ și cu probabilitate în jur $2^{-38}$ primii 188 de biți se vor potrivi. Acest lucru oferă un buget total de lucru de 44-45 de biți de teste de primalitate. Metoda lui Joye se va îmbunătăți cu siguranță, dar analiza va fi mai lungă.

Pentru intrebarea generala cu $q\aproximativ\rădăcină 4\din n$ și lungimea intervalului $\rădăcină 8\din n$, ne-am aștepta în jur $\frac14\root 8\of n\log n$ teste de primalitate ale numerelor din jur $\rădăcină 4\din n$ în dimensiune pentru metoda folclorului, dar din nou Joye ar trebui să îmbunătățească acest lucru.

Dacă utilizați funcții de factoring existente, acest lucru poate fi rezolvat în câteva minute pentru numere aleatoare de 200 de biți. Funcții de factoring de la Pari/GP, de exemplu.

Algoritmul de mai jos nu este doar factorizarea numerelor consecutive. Vezi mai jos.

Iată algoritmul general care a fost convertit într-un lucru program:

Generați W, un număr aleatoriu de 200 de biți

sievelimit = 250 limită primă = 2000000

precalcul pr = produsul primelor prime limită primă

Pentru n1 = W+1 la W+limită de sită

Dacă n1 este de forma 6k+1 sau 6k+5

 dacă gcd(n1,pr) este 1

   f = factor(n1)

      dacă numărul de factori ai lui n1 este 2 și ambii >2^50   
          imprimare Soluție f  

Buclă

Linia:

dacă gcd(n1,pr) este 1

este o modalitate rapidă de a omite numerele care au factori primi sub 2 milionea primă.

Pasul de precalculare este optimizat în Pari/GP și durează doar 7.785 secunde pe hardware lent.

Pentru cel mai rău caz, un număr de 200 de biți, funcția factor din Pari/GP utilizează metoda MPQS și durează mai puțin de 30 de secunde pe hardware vechi.

Iată un număr aleator de 200 de biți W: 1567470448908230034126591070540826459978233372650796513704199

Programul factorizează doar un număr W+10 și găsește soluția

p1 = 5346955435967300929
p2 = 293151956787285973328498761492202409914321  

p1 este de 63 de biți, p2 este de 138 de biți, n = p1*p2

|W-n| = 10, |W-n|< 2^12