Kontroler pierwszości

Funkcja sprawdzania pierwszości informuje, czy liczba całkowita jest liczbą pierwszą, i – w przeciwieństwie do większości kalkulatorów dostępnych w Internecie – pokazuje rzeczywisty algorytm, który to udowodnił, a nie buforowaną tabelę przeglądową. Wpisz dowolną liczbę całkowitą, dodatnią lub ujemną, małą lub ogromną, a narzędzie na podstawie jej rozmiaru zdecyduje, który rzeczywisty algorytm ma zostać uruchomiony.

W przypadku liczb poniżej 10¹² (jeden bilion) przeprowadza prawdziwe dzielenie próbne: zaczynając od 2, wypróbowuje każdą liczbę całkowitą aż do podłogi √n jako możliwy dzielnik, zatrzymując moment, w którym dzieli się równomiernie (złożony) lub potwierdzając, że nikt tego nie robi, po sprawdzeniu każdego kandydata do √n (liczba pierwsza). W przypadku dużej liczby kandydatów pokazany ślad jest ograniczony do pierwszych ~18 prób plus ostatnia, z rzetelną notatką o tym, ilu kandydatów zostało pominiętych na wyświetlaczu — ale każdy kandydat jest nadal faktycznie sprawdzany przez kod, żaden nie jest pomijany w obliczeniach.

W przypadku liczb na poziomie lub powyżej tego progu — zakresu rozmiarów stosowanego w kryptografii — próbny podział zająłby zbyt dużo czasu, dlatego narzędzie przełącza się na test pierwszości Millera-Rabina ze stałym, deterministycznym zestawem 13 głównych świadków (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Ten dokładny zbiór świadków jest dobrze znanym wynikiem: nie ma fałszywych alarmów dla żadnego n poniżej 3 317 044 064 679 887 385 961 981 (około 3,3 × 10²⁴), co stanowi granicę ustaloną w drodze weryfikacji obliczeniowej (patrz Sorenson i Webster, 2015 oraz szeroko reprodukowana tabela świadków deterministycznych, do której należy). Powyżej tej granicy nadal przeprowadzany jest ten sam test, ale narzędzie szczerze mówi, że gwarancja staje się niezwykle silną gwarancją probabilistyczną, a nie matematyczną.

Ślad Millera – Rabina zapisuje n - 1 = 2ˢ × d z d nieparzystym, następnie przechodzi przez prawdziwe potęgowanie modułowe BigInt - podnosząc do kwadratu i mnożąc, redukując modulo n na każdym kroku, aby liczby nigdy nie eksplodowały - krok po kroku dla pierwszego świadka i podaje werdykt każdego świadka, łącznie z tym, który świadek udowodni złożoność, jeśli okaże się, że liczba nie jest pierwsza. Wszystko działa lokalnie w Twojej przeglądarce: żaden serwer, żadne zewnętrzne API, żadne dane nie opuszczają Twojego urządzenia.