Kalkulator testu pierwszości Millera-Rabina

O tym kalkulatorze

Test Millera-Rabina sprawdza pierwszość, zapisując n − 1 jako 2ˢ·d z nieparzystym d, a następnie badając, czy baza-świadek a spełnia aᵈ ≡ 1 (mod n) lub a^(2ʳ·d) ≡ −1 (mod n) dla pewnego r < s. Pojedynczy świadek daje tylko wynik probabilistyczny, ale testowanie względem małego, udowodnionego zbioru stałych baz-świadków (na przykład 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) sprawia, że test jest deterministyczny dla każdej liczby całkowitej poniżej około 3,18 × 10²³ — daleko poza tym, czego potrzebuje większość zastosowań.

Kryptografowie i programiści używają dokładnie tego rodzaju testu przy generowaniu dużych kandydatów na liczby pierwsze dla kluczy RSA lub Diffiego-Hellmana, a studenci informatyki — aby zobaczyć na prawdziwych liczbach, dlaczego test Millera-Rabina skaluje się o wiele lepiej niż dzielenie próbne przy sprawdzaniu, czy duża liczba całkowita jest pierwsza.