Test pierwszości
Sprawdź, czy liczba jest pierwsza i zobacz dokładnie dlaczego: prawdziwe dzielenie próbne do √n dla małych i średnich liczb oraz szczegółowy test Millera–Rabina dla liczb rzędu kryptograficznego.
🔒 Przetwarzane w całości w Twojej przeglądarce — nic, co tu wpiszesz, nie zostanie nigdy przesłane.
Wynik
Narzędzie do testowania pierwszości liczb powie Ci, czy liczba całkowita jest pierwsza, i — w przeciwieństwie do większości kalkulatorów online — pokazuje rzeczywisty algorytm, który to udowodnił, a nie zapisaną w pamięci podręcznej tabelę. Wpisz dowolną liczbę całkowitą, dodatnią lub ujemną, małą czy ogromną, a narzędzie samo zadecyduje, który prawdziwy algorytm uruchomić, na podstawie jej rozmiaru.
Dla liczb poniżej 10¹² (jeden bilion) uruchamiane jest prawdziwe dzielenie próbne: począwszy od 2, narzędzie sprawdza każdą kolejną liczbę całkowitą aż do podłogi z √n jako potencjalny dzielnik, kończąc w momencie, gdy któraś podzieli liczbę bez reszty (liczba złożona), albo potwierdzając, że żadna tego nie robi, gdy wszyscy kandydaci do √n zostali już sprawdzeni (liczba pierwsza). Dla ogromnej liczby kandydatów pokazany ślad jest ograniczony do pierwszych ~18 sprawdzonych plus ostatniego, z uczciwą informacją, ile zostało pominiętych na wyświetlaczu — ale każdy jeden kandydat jest faktycznie sprawdzany przez kod, żaden nie jest pomijany w obliczeniach.
Dla liczb równych lub większych od tego progu — czyli z zakresu stosowanego w kryptografii — dzielenie próbne trwałoby zbyt długo, więc narzędzie przełącza się na test pierwszości Millera–Rabina ze stałym, deterministycznym zestawem 13 liczb pierwszych jako świadków (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Ten konkretny zestaw świadków to dobrze znany wynik: nie daje on fałszywych wyników pozytywnych dla żadnego n poniżej 3 317 044 064 679 887 385 961 981 (około 3,3×10²⁴), co jest ograniczeniem ustalonym przez weryfikację obliczeniową (patrz Sorenson i Webster, 2015, oraz szeroko reprodukowana tabela deterministycznych świadków, do której należy). Powyżej tego ograniczenia test nadal jest uruchamiany, ale narzędzie informuje uczciwie, że gwarancja staje się niezwykle silnym prawdopodobieństwem, a nie matematyczną pewnością.
Ślad testu Millera–Rabina zapisuje n − 1 = 2ˢ × d z nieparzystym d, a następnie przechodzi przez rzeczywiste potęgowanie modularne BigInt — metoda 'podnieś do kwadratu i pomnóż', redukcja modulo n w każdym pojedynczym kroku, aby liczby nigdy nie eksplodowały — bit po bicie dla pierwszego świadka, i raportuje werdykt każdego świadka, w tym który świadek dowodzi złożoności, jeśli liczba okaże się nie być pierwsza. Wszystko działa lokalnie w Twojej przeglądarce: żaden serwer, żadne zewnętrzne API, żadne dane nigdy nie opuszczają Twojego urządzenia.