Primitātes pārbaudītājs

Primalitātes pārbaudītājs norāda, vai vesels skaitlis ir galvenais, un atšķirībā no vairuma tiešsaistes kalkulatoru parāda faktisko algoritmu, kas to pierādīja, nevis kešatmiņā saglabātu uzmeklēšanas tabulu. Ievadiet jebkuru veselu skaitli, pozitīvu vai negatīvu, mazu vai milzīgu, un rīks izlemj, kuru reālo algoritmu palaist, pamatojoties uz tā lielumu.

Skaitļiem, kas ir mazāki par 10¹² (viens triljons), tas veic īstu izmēģinājuma dalījumu: sākot no 2, tas izmēģina katru veselu skaitļu līdz √n zemākajai daļai kā iespējamo dalītāju, apturot brīdi, kad viens dalās vienmērīgi (salikts) vai apstiprinot, ka neviens nedalās, tiklīdz ir pārbaudīts katrs kandidāts līdz √n. Milzīgam kandidātu skaitam parādītā izsekošana tiek ierobežota līdz pirmajiem ~18 izmēģinājumiem un pēdējam, ar godīgu piezīmi par to, cik daudz tika izlaists displejā, taču katrs kandidāts joprojām faktiski tiek pārbaudīts pēc koda, neviens netiek izlaists aprēķinos.

Skaitļiem, kas atbilst vai pārsniedz šo slieksni — kriptogrāfijā izmantoto izmēru diapazonu — izmēģinājuma dalīšana aizņemtu pārāk ilgu laiku, tāpēc rīks pārslēdzas uz Millera–Rabina pirmatnības testu ar fiksētu, deterministisku 13 galveno liecinieku kopu (2, 3, 5, 7, 11, 13, 17, 19, 9, 3, 3). Šī precīzā liecinieku kopa ir labi zināms rezultāts: tai nav viltus pozitīvu rezultātu nevienam n, kas ir mazāks par 3 317 044 064 679 887 385 961 981 (apmēram 3,3 × 10²⁴), kas noteikta ar skaitļošanas verifikāciju (skatiet Sorenson & Webster, retermined tabulu un deterministisko 20.15. pieder). Virs šīs robežas joprojām tiek izpildīts tas pats tests, taču rīks godīgi pasaka, ka garantija kļūst par ārkārtīgi spēcīgu varbūtību, nevis matemātisku noteiktību.

Millera–Rabina izsekošana raksta n − 1 = 2ˢ × d ar d odd, pēc tam iziet cauri reālai BigInt moduļu kāpināšanai — kvadrātā un reizinā, samazinot modulo n katrā atsevišķā solī, lai skaitļi nekad neeksplodētu — pa bitam pirmajam lieciniekam, un ziņo katra liecinieka salikto spriedumu, ja liecinieka spriedums izrādās neveiksmīgs. Viss darbojas lokāli jūsu pārlūkprogrammā: nav servera, nav ārēja API, nekādi dati nekad nepamet jūsu ierīci.