Ho appena risposto alla stessa domanda su StackOverflow, quindi duplicherò la mia risposta qui (non penso che la duplicazione sia la strada da percorrere, forse la domanda dovrebbe essere migrata):
Supponiamo che tu scelga un primo p selezionando valori casuali fino a quando non ne colpisci uno per cui Miller-Rabin dice: quello sembra un numero primo. Usi n al massimo per il test Miller-Rabin. (Per un cosiddetto "sicuro primo", le cose non sono cambiate, tranne che esegui due test annidati.)
La probabilità che un numero casuale di 1024 bit sia primo è circa 1/900. Ora, non vuoi fare nulla di stupido in modo da generare solo valori dispari (un intero pari a 1024 bit è garantito non-prime) e, più in generale, esegui solo il test di Miller-Rabin se il valore non è "ovviamente" non primo, cioè può essere diviso per un piccolo primo. Quindi finisci col provare circa 300 valori con Miller-Rabin prima di colpire un numero primo (in media). Quando il valore non è primo, Miller-Rabin lo rileverà con probabilità 3/4 ad ogni round, quindi il numero di round Miller-Rabin che eseguirai in media per un singolo valore non primo è 1+ (1/4 ) + (1/16) + ... = 4/3. Per i 300 valori, ciò significa circa 400 round di Miller-Rabin, indipendentemente da ciò che si sceglie per n .
( Modifica: in realtà, per un non-scelto a caso, Miller-Rabin funziona meglio di così (vedi la risposta di @ Brett) e il numero medio di round sarà più vicino a 300 di 400. Non cambia sostanzialmente la mia argomentazione.)
Quindi, se si seleziona n , ad esempio 40, il costo implicito da n è inferiore al 10% del costo computazionale totale. Il processo casuale di selezione del primo è dominato dal test sui non-primi, che non sono influenzati dal valore di n che scegli. Ho parlato qui di interi a 1024 bit; per i numeri più grandi la scelta di n è ancora meno importante dato che i numeri diventano più spartani all'aumentare delle dimensioni (per gli interi a 2048 bit, il "10%" diventa "5%").
Quindi puoi scegliere n = 40 e accontentarti (o almeno sapere che ridurre n non ti comprerà comunque molto). D'altra parte, usare un n superiore a 40 non ha senso, perché ciò ti porterebbe a probabilità inferiori al rischio di un semplice calcolo errato. I computer sono hardware, possono avere guasti casuali. Ad esempio, una funzione di test di primalità potrebbe restituire "vero" per un valore non primo poiché un raggio cosmico (una particella ad alta energia che sfreccia attraverso l'universo ad alta velocità) si trova a colpire il transistor giusto al momento giusto, invertendo il restituisce il valore da 0 ("false") a 1 ("true"). Questo è molto improbabile, ma non meno probabile della probabilità 2 -80 . Vedi questa risposta StackOverflow per qualche altro dettaglio. La linea di fondo è che, indipendentemente da come ti assicuri che un numero intero sia primo, hai ancora un elemento probabilistico inevitabile, e 40 round di Miller-Rabin ti danno già il meglio che puoi sperare.
Per riassumere, usa 40 colpi.