Calculator test de primalitate Miller-Rabin

Despre acest calculator

Testul Miller-Rabin verifică primalitatea scriind n − 1 ca 2ˢ·d cu d impar, apoi testând dacă o bază martor a satisface aᵈ ≡ 1 (mod n) sau a^(2ʳ·d) ≡ −1 (mod n) pentru un anumit r < s. Un singur martor dă doar un rezultat probabilistic, dar testarea cu un set mic, demonstrat, de baze martor fixe (de exemplu 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) face testul determinist pentru orice număr întreg sub aproximativ 3,18 × 10²³ — mult peste ceea ce au nevoie vreodată majoritatea aplicațiilor.

Criptografii și dezvoltatorii de software folosesc exact acest gen de test când generează candidați mari de numere prime pentru chei RSA sau Diffie-Hellman, iar studenții la informatică îl folosesc pentru a vedea, pe numere reale, de ce Miller-Rabin se scalează mult mai bine decât împărțirea de probă la verificarea primalității unui număr întreg mare.