Sită cuadratică: Există o regulă pentru degetul mare pentru a decide câte numere să cerne?

În sita cuadratică pură, trebuie să găsim puțin mai multe relații (echivalent, netezi) decât există numere prime în baza factorilor. În aceasta, numărăm numerele prime mici $p_i$ care fac $N$ un reziduu patratic modulo $p_i$, nu puterile lor. Acest număr este, de asemenea, numărul de coloane din matricea (rară) de relații, unde relațiile sunt linii, care servește ca intrare în faza algebrei liniare. De obicei, cu 5 linii mai multe decât coloane vor fi suficiente. Fiecare relație suplimentară scade probabilitatea de eșec cu un factor de doi.

Acest lucru oferă un criteriu de lucru pentru a opri cernerea și a începe algebra liniară, dar nu spune direct de câte numere întregi va trebui să cerem. Regula de bază pentru asta și alți parametri depinde de multe lucruri, inclusiv

• În mod critic, dacă cernem unul (QS) sau mai multe polinoame (MPQS/SIQS). Cu QS, prea des se întâmplă ca polinomul să crească la valori prea mari, astfel încât netezirile să devină o raritate; apoi, mărirea sitei sau refolosirea ei pentru a cerne mai departe pe același polinom nu va ajuta prea mult.
• Strategia w.r.t. valori polinomiale de care nu suntem siguri (sau foarte încrezători), însumând logarii factorilor lor găsiți prin cerne, că sunt suficient de netede pentru scopurile noastre. Noi putem
  • Ignoră-i, chiar dacă ar mai putea fi $B$-neted.
  • Încercați factori primi mici până la cel mai înalt cernut $B$, și puterile lor chiar dacă depășesc $B$ (cu alte cuvinte, ne limităm la $B$-valori netede ale polinomului care a trecut de pasul de cernere); este ușor și tipic pentru QS de bază (MP/SI).
  • Încercați factori mici până la o limită mai mare $B'$ (cu alte cuvinte, cernem puterile prime și prime pentru $B<B'$, și restricționați la $B'$-netezi care au trecut de treapta de cernere).
  • În plus, permiteți un factor prim mare (PMPQS) la o limită mai mare, în speranța că o coliziune pentru aceste numere prime mari va permite două relații altfel inutilizabile să producă una nouă utilizabilă (adică fără prim mare, astfel încât să se potrivească cu numărul limitat de coloane din matricea)
  • În plus, permiteți doi factori primi mari (PPMPQS).
• Pragul de cernere (pentru suma logaritmilor primelor acumulate în intrarea prin sită), care este un compromis între respingere $B$- netezește și petrecând prea mult timp încercând să factorizeze candidații care nu vor genera relații utilizabile.

Recomandări pentru ca QS să funcționeze:

• Mai întâi fă ceva modest $N$ fără sită!
  • Utilizați o bază de factori de $p_i$ realizarea $N$ un reziduu pătratic, până la o anumită limită $B$. Este mai sigur să greșești mai întâi pe partea mare a optimului $B$.
  • Găsi $B$- netezeste intre valorile polinomului $t^2-N$ cu $t\gtsim\left\lceil\sqrt N\,\right\rceil$ printr-un mod cel mai elementar (de exemplu, divizia de judecată).Găsiți puțin mai multe netezi decât numere prime.
  • Faceți ca algebra liniară să funcționeze la factorizare $N$.
• Optimizați majoritatea (sau toate) diviziile de încercare ale $t^2-N$ printr-un test care $t\bmod(p_i^k)$ se încadrează într-un set de două valori precalculate.
• În această etapă, blocajul ar trebui să găsească soluții prin încercarea de a factoriza pe deplin multe $t^2-N$ folosind divizia de încercare (optimizată), majoritatea ajungând să nu fie $B$-neted. Introduceți matricea sieve, care are ca scop reducerea (dramatic) a numărului de candidați netezi, cu prețul respingerii greșit a câțiva candidați (cernerea pentru puterile prime ajută la rarirea respingerii false). Acest lucru permite creșterea $N$ (creind astfel optimul $B$).
• Introduceți optimizări suplimentare una câte una:
  • având $-1$ în baza factorilor, adică și cernerea $N-t^2$ pentru $t\lesssim\left\lfloor\sqrt N\,\right\rfloor$
  • imbunatatirea usoara „multiplicator”, care factori $m\,N$ pentru un număr întreg mic selectat $m$, astfel încât baza factorilor este îmbunătățită (are relativ multe numere prime mici)
  • folosind polinoame multiple, ceea ce permite cernerea și factorizarea candidaților mult mai mici, astfel mai probabil să fie $B$- netezeste
  • gâtul de strângere poate fi încă încercat factorizarea netedelor care au trecut testul de sită (în funcție de pragul de cernere și de dimensiunea bazei factorilor); unele economii sunt posibile folosind diviziunea de probă (optimizată) numai prin numere prime mici, apoi ceva mai bun, poate rho lui Pollard cu un test de primalitate când nu cedează repede; un astfel de test va fi necesar pentru îmbunătățirile primelor mari.
  • una, apoi două îmbunătățiri principale mari (PMPQS și PPMPQS).
• Optimizați orice blocaj este și reglați numeroșii parametri. În cele din urmă, blocajul ar trebui să fie cernut. Implementările optimizate fac mult efort acolo, cu tehnici și coduri specializate în funcție de dimensiunea primelor cernute și interacțiunea cu cache-urile CPU.