Pirmskaitļu pārbaudītājs
Pārbaudiet, vai skaitlis ir pirmskaitlis, un redziet precīzu pamatojumu: reāla dalītāju pārbaude līdz √n maziem un vidējiem skaitļiem un pilns Millera–Rabina algoritma izklāsts kriptogrāfiski lieliem skaitļiem.
🔒 Pilnībā apstrādāts jūsu pārlūkprogrammā — nekas, ko jūs šeit ievadāt, nekad netiek augšupielādēts.
Rezultāts
Šis pirmskaitļu pārbaudītājs parāda, vai vesels skaitlis ir pirmskaitlis, un — atšķirībā no vairuma tiešsaistes kalkulatoru — parāda reālo algoritmu, kas to pierādīja, nevis saglabātu uzmeklēšanas tabulu. Ievadiet jebkuru veselu skaitli — pozitīvu vai negatīvu, mazu vai milzīgu —, un rīks izvēlas, kuru algoritmu izmantot, pamatojoties uz tā lielumu.
Skaitļiem, kas mazāki par 10¹² (viens triljons), tiek veikta reāla dalītāju pārbaude: sākot ar 2, katrs vesels skaitlis līdz √n tiek pārbaudīts kā iespējams dalītājs, apstājoties, tiklīdz kāds dalās bez atlikuma (salikts skaitlis), vai apstiprinot, ka tāda nav, kad pārbaudīts viss līdz √n (pirmskaitlis). Ja iespējamo dalītāju skaits ir milzīgs, attēlotais izsekojums tiek samazināts līdz pirmajiem ~18 plus pēdējam, ar godīgu piezīmi par to, cik daudzi izlaisti rādīšanā — tomēr kods joprojām pārbauda visus iespējamos dalītājus, neviens netiek izlaists aprēķinos.
Skaitļiem, kas ir vienādi ar šo slieksni vai lielāki — diapazonā, ko izmanto kriptogrāfijā — dalītāju pārbaude aizņemtu pārāk ilgu laiku, tāpēc rīks pārslēdzas uz Millera–Rabina pirmskaitļu testu ar fiksētu, deterministisku 13 pirmskaitļu liecinieku kopu (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Šī precīzā liecinieku kopa ir plaši pazīstams rezultāts: tai nav kļūdaini pozitīvu rezultātu nevienam n zem 3 317 044 064 679 887 385 961 981 (aptuveni 3,3×10²⁴) — robeža, kas noteikta ar skaitļošanas pārbaudi (skatīt Sorenson & Webster, 2015, un plaši izplatīto deterministisko liecinieku tabulu, pie kuras tas pieder). Virs šīs robežas tests joprojām darbojas, bet rīks godīgi norāda, ka garantija kļūst par ļoti spēcīgu varbūtības garantiju, nevis matemātisku noteiktību.
Millera–Rabina izsekojums uzraksta n − 1 = 2ˢ × d, kur d ir nepāra, tad soli pa solim — pa bitiem — izpilda reālu BigInt modulāro kāpināšanu (reizināt un kvadrēt, reducējot pēc moduļa n katrā solī, lai skaitļi nekļūtu pārāk lieli) pirmajam lieciniekam, un ziņo par katra liecinieka spriedumu, ieskaitot to, kurš liecinieks pierāda salikta skaitļa dabu, ja skaitlis nav pirmskaitlis. Viss darbojas lokāli jūsu pārlūkā: nav servera, nav ārēja API, nekādi dati nepamet jūsu ierīci.