Verificator de primalitate

Verificatorul de primalitate vă spune dacă un număr întreg este prim și, spre deosebire de majoritatea calculatoarelor online, vă arată algoritmul real care a demonstrat acest lucru, nu un tabel de căutare în cache. Tastați orice număr întreg, pozitiv sau negativ, mic sau enorm, iar instrumentul decide ce algoritm real să ruleze în funcție de dimensiunea acestuia.

Pentru numere sub 10¹² (un trilion), rulează o diviziune de probă autentică: începând cu 2, încearcă fiecare candidat întreg până la etajul √n ca posibil divizor, oprindu-se în momentul în care se împarte uniform (compozit) sau confirmând că niciunul nu face odată ce fiecare candidat până la √n a fost verificat (prim). Pentru un număr mare de candidați, urma afișată este limitată la primele ~18 încercate plus cea finală, cu o notă sinceră despre câți au fost omise pe afișaj - dar fiecare candidat este încă verificat de cod, niciunul nu este omis în calcul.

Pentru numere la sau peste acel prag - intervalul de dimensiuni utilizate în criptografie - diviziunea de probă ar dura prea mult, astfel încât instrumentul trece la testul de primalitate Miller-Rabin cu un set fix, determinist de 13 martori primi (2, 3, 5, 7, 11, 13, 17, 19, 23, 3, 11, 3, 3, 12). Acest set de martori exact este un rezultat binecunoscut: nu are false pozitive pentru niciun n sub 3.317.044.064.679.887.385.961.981 (aproximativ 3,3 × 10²⁴), o limită stabilită prin verificare computațională (vezi Sorenson & Webster, tabelul deterministic și reproducerea pe scară largă a acestuia, 2015). Peste această limită se execută în continuare același test, dar instrumentul vă spune sincer că garanția devine mai degrabă una probabilistică extrem de puternică decât o certitudine matematică.

Urma Miller-Rabin scrie n − 1 = 2ˢ × d cu d impar, apoi parcurge exponentiația modulară BigInt reală - pătrat și înmulțire, reducând modulo n la fiecare pas, astfel încât numerele să nu explodeze niciodată - bit cu bit pentru primul martor și raportează verdictul fiecărui martor, inclusiv care martor se dovedește că nu este un număr prim. Totul rulează local în browserul dvs.: niciun server, niciun API extern, nicio dată nu părăsește dispozitivul dvs.