Sunt conștient de faptul că testul de primalitate MillerâRabin va revendica primalitatea pentru un număr compus cu cel mult A $\frac{1}{4}$ probabilitate pentru un compus arbitrar, ciudat $n$ și un martor la întâmplare $a$ alese uniform în gamă $[2,n-1)$. Ce este real șansa medie ca testul să pretindă în mod fals că numărul este prim? Cum se schimbă șansa în funcție de dimensiunea $n$ merge în sus? Cum se schimbă șansa dacă $n$ nu este divizibil cu numere prime mici până la, să zicem, 2000?
întreb pentru că această hârtie descrie probabilitatea ca un compozit să supraviețuiască unui număr de runde de testare. Probabilitatea este $p_{k,t}$ cu $k$ fiind mărimea numărului de testat în biţi şi $t$ fiind numărul de runde de rulat. Lucrarea dovedește că $\forall k \ge 2:p_{k,1} \le k^2 4^{2-\sqrt{k}}$, dar această inegalitate este doar o limită superioară și există o dovadă separată pentru a arăta limita mult mai puternică $p_{600,1} \le 2^{-75}$. Aș dori să găsesc o funcție cu o limită superioară puternică pentru $p_{k,t,n}$ cu $n$ fiind diviziunea de probă împotriva tuturor primelor mai mici decât $n$, dar nu înțeleg suficient de bine matematica din spatele acestei lucrări pentru a veni cu asta.
Tabelul 2 din lucrare oferă câteva exemple de limite inferioare pentru $-\lg{p_{k,t}}$:
\begin{matrice}{c|ccccccccc}
k/t&1&2&3&4&5&6&7&8&9&10\ \hline
100&5&14&20&25&29&33&36&39&41&44\
150&8&20&28&34&39&43&47&51&54&57\
200&11&25&34&41&47&52&57&61&65&69\
250&14&29&39&47&54&60&65&70&75&79\
300&19&33&44&53&60&67&73&78&83&88\
350&28&38&48&58&66&73&80&86&91&97\
400&37&46&55&63&72&80&87&93&99&105\
450&46&54&62&70&78&85&93&100&106&112\
500&56&63&70&78&85&92&99&106&113&119\
550&65&72&79&86&93&100&107&113&119&126\
600&75&82&88&95&102&108&115&121&127&133
\end{matrice}
Generarea de chei OpenSSL pare să presupună că nu este cazul, deoarece crește numărul de runde pentru numere prime mai mari, sub iluzia că rata fals pozitive afectează cumva securitatea primelor generate. Rețineți că acest cod este folosit în prima generaţie de rutină, astfel încât numerele prime candidate sunt garantate a fi distribuite uniform și nu sunt supuse ratei fals-pozitive în cel mai rău caz.
Din crypto/bn/bn_prime.c:87:
/*
* Folosiți un minim de 64 de runde de Miller-Rabin, care ar trebui să dea un fals
* rata pozitivă de 2^-128. Dacă dimensiunea primului este mai mare decât 2048
* utilizatorul dorește probabil un nivel de securitate mai mare decât 128, așa că comutați
* la 128 de runde dând o rată fals pozitivă de 2^-256.
* Returnează numărul de runde.
*/
static int bn_mr_min_checks(int biți)
{
dacă (biți > 2048)
întoarcere 128;
întoarcere 64;
}
