Numărul de numere întregi impare până la care trebuie să testăm pentru a găsi unul care este prim pentru orice dimensiune arbitrară a modulului RSA

Dimensiunile populare ale modulului RSA sunt $1024$, $2048$, $3072$ și $4092$ pic. Câte numere întregi impare aleatoare trebuie să testăm în medie până când ne așteptăm să găsim unul care este prim? Cunosc cam pe fiecare $\ln p$ numerele întregi au un prim. Pentru o $1024$ pic $p$, $\ln p = 710$. În medie, trebuie să testați aproximativ $710/2=355$ numere impare înainte de a găsi un prim. Este adevărat și putem extrage formula $(\ln p)/2$ pentru orice dimensiune arbitrară a modulului RSA?

Pentru RSA pe n biți, trebuie să găsiți două numere prime al căror produs este un număr de n biți, adică aproximativ n/2 biți fiecare. De fapt, unul puțin mai mic și unul puțin mai mare, pentru că nu doriți ca numerele prime să fie prea apropiate.

Aproximativ unul din ln M numere din jurul lui M este prim; acesta este logaritmul natural. Ln (2) este aproape de 0,7. Dacă M = 2^(n/2), atunci ln M â 0,35n. Verificați numai numere întregi impare care au de două ori mai multe șanse să fie prime, cu probabilitatea 2 / 0,35n. Testarea a 0,175n numere întregi impare găsește un prim. Ai nevoie de două, deci aproximativ 0,35n.

Dar rețineți că mulți dintre aceștia au divizori mici și pot fi identificați foarte repede; de exemplu prin folosirea unei site care elimină numerele cu factori < 1000 sau 10.000. Pentru a accepta un prim, veți rula testul Miller-Rabin de 50 sau 100 de ori, în timp ce pentru 3/4 dintre non-prime îl rulați o dată, pentru 3/4 din restul îl rulați de două ori etc. Ideea este că testarea unui non-prime pentru primalitate este de obicei destul de rapidă.Testarea celor două numere prime reale durează mult timp. Numărul de compozite pe care le testați pentru primalitate nu contează prea mult.

PS Tocmai mi-am dat seama că toată lumea supraestimează cu un factor 2. Să zicem că am decis că vreau un prim aproape de un K impar, așa că testez K, K+2, K+4 etc până mă întâlnesc cu un prim. Fie p cel mai mare prim mai mic decât K și q primul prim >= K. Numărul de numere off de testat nu este decalajul q-p, împărțit la 2 (pentru că testăm doar numere impare), ci jumătate, deoarece K poate fi oriunde în acel gol.

PPS Tocmai mi-am dat seama că este ceva în neregulă cu acel argument...

Nu, te înșeli, pentru că

Știu că aproximativ fiecare ln p numere întregi au un prim.

este o estimare aproximativă, care este de fapt greșită.

Estimarea funcției de numărare a primelor $\Pi(p)=p /ln(p)$ estimează numerele prime totale între 0 și $p$. Deci, pentru un număr cu x biți, trebuie să vă uitați la $\Pi(2^{x}) - \Pi(2^{x-1})$ și comparați-l cu numărul total de candidați, care sunt $2^{x-2}$, când luați în considerare doar numerele impare.

Nu ești departe, iar diferența este mică pentru numere mari, dar formula nu este atât de simplă.