Testul Miller-Rabin

Testul de primărie Miller-Rabin este un test de primărie , care este un algoritm pentru a determina dacă un număr întreg este prim . Versiunea sa originală, datorită lui Gary Miller , este deterministă, dar depinde de ipoteza generalizată Riemann , o conjectură matematică importantă încă deschisă. Algoritmul a fost modificat ulterior de Michael Rabin, care a obținut o versiune probabilistică similară cu testul Fermat și testul Solovay-Strassen .

Definiție

Fie n un număr întreg pozitiv ciudat și nu un prim. Numerele pozitive b <n astfel încât GCD (b, n) = 1, și astfel încât n să fie un pseudoprim Euler puternic în baza b nu depășesc un sfert din toate numerele pozitive b <n astfel încât GCD (b, n) = 1.

Acesta este testul de primărie pe care îl prezentam:

Dacă repar un număr întreg n> 1, îl pot scrie ca $n=2^{s}*t+1$ ${\ displaystyle n = 2 ^ {s} * t + 1}$ ${\ displaystyle n = 2 ^ {s} * t + 1}$ , cu t impar. Testul T. $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ se rezumă în următoarele:

alegem aleatoriu un număr întreg b $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ , cu 1 <b $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ <n și calculăm GCD (b $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ , n);
dacă MCD (b $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ , n)> 1, atunci n nu este prim și am terminat;
dacă MCD (b $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ , n) = 1, calculăm b $_{1}^{t}$ ${\ displaystyle _ {1} ^ {t}}$ ${\ displaystyle _ {1} ^ {t}}$ (formularul n). Dacă b $_{1}^{t}$ ${\ displaystyle _ {1} ^ {t}}$ ${\ displaystyle _ {1} ^ {t}}$ ≡ +1 (mod n) sau b $_{1}^{t}$ ${\ displaystyle _ {1} ^ {t}}$ ${\ displaystyle _ {1} ^ {t}}$ ≡ -1 (mod n), n este pseudoprimul prim sau puternic în baza b $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ ;
dacă nu este adevărat că b $_{1}^{t}$ ${\ displaystyle _ {1} ^ {t}}$ ${\ displaystyle _ {1} ^ {t}}$ ≡ +1 (mod n) sau b $_{1}^{t}$ ${\ displaystyle _ {1} ^ {t}}$ ${\ displaystyle _ {1} ^ {t}}$ ≡ -1 (mod n), calculăm b $_{1}^{2t}$ ${\ displaystyle _ {1} ^ {2t}}$ ${\ displaystyle _ {1} ^ {2t}}$ (formularul n). Dacă b $_{1}^{2t}$ ${\ displaystyle _ {1} ^ {2t}}$ ${\ displaystyle _ {1} ^ {2t}}$ ≡ -1 (mod n), atunci n este pseudoprimă puternică în baza b $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ ;
dacă nu este adevărat că b $_{1}^{2t}$ ${\ displaystyle _ {1} ^ {2t}}$ ${\ displaystyle _ {1} ^ {2t}}$ ≡ -1 (mod n), trecem ab $_{1}^{4t}$ ${\ displaystyle _ {1} ^ {4t}}$ ${\ displaystyle _ {1} ^ {4t}}$ , și pentru toate celelalte puteri de 2, înmulțite cu t. Dacă toate ib $_{1}^{2^{r}*t}$ ${\ displaystyle _ {1} ^ {2 ^ {r} * t}}$ ${\ displaystyle _ {1} ^ {2 ^ {r} * t}}$ , pentru r = 1, ..., s-1, nu sunt niciodată congruente cu -1 modul n, atunci $n$ ${\ displaystyle n}$ $n$ nu este o premieră. Altfel n este un pseudoprim puternic în baza b $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ .

Pentru toate celelalte teste {T $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ } $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ , m∈ $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ ${\ displaystyle \ mathbb {N}}$ , definiția este similară:

alegem aleatoriu un număr întreg b $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ , cu 1 <b $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ <n și calculăm GCD (b $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ , n);
dacă MCD (b $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ , n)> 1, atunci n nu este prim și am terminat;
dacă MCD (b $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ , n) = 1, calculăm b $_{m}^{t}$ ${\ displaystyle _ {m} ^ {t}}$ ${\ displaystyle _ {m} ^ {t}}$ (mod n) și continuați ca la primul test. În acest fel, constatăm că n nu este prim sau că n este un pseudoprim puternic în baza b $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ .

Ultimele gânduri despre test

Se poate observa imediat că, spre deosebire de testele lui Fermat și Wilson , aici calculele sunt mai puține ca număr și mult mai simple și se poate demonstra că nivelul de complexitate de calcul este polinomial, în timp ce celelalte două prezintă o dificultate de calcul exponențială. În ceea ce privește fiabilitatea, este foarte bună și la acest test. De fapt, în ciuda faptului că este un test probabilistic, atunci când efectuăm testul T. $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ , știm că probabilitatea ca n să nu fie prim și să fie un pseudoprim puternic în baza b $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ este mai mic de 1/4 și, prin urmare, probabilitatea ca n să nu fie prim, dar să treacă testele T $_{1}$ ${\ displaystyle _ {1}}$ $_ {1}$ , T $_{2}$ ${\ displaystyle _ {2}}$ $_ {2}$ , ..., T $_{m}$ ${\ displaystyle _ {m}}$ ${\ displaystyle _ {m}}$ e mai puțin decât $\left({\frac {1}{4^{m}}}\right)$ ${\ displaystyle \ left ({\ frac {1} {4 ^ {m}}} \ right)}$ ${\ displaystyle \ left ({\ frac {1} {4 ^ {m}}} \ right)}$ , adică foarte mic în comparație cu testul Fermat .

Presupunând ipoteza generalizată Riemann , testul Miller-Rabin poate fi ușor modificat pentru a deveni un adevărat test de primalitate, iar algoritmul asociat ar costa $O((\log n)^{4}\log \log \log n)$ ${\ displaystyle O ((\ log n) ^ {4} \ log \ log \ log n)}$ ${\ displaystyle O ((\ log n) ^ {4} \ log \ log \ log n)}$ ^[1] .