Провера прималности
Проверите да ли је број прост и видите тачно зашто: право пробно дељење до √n за мале и средње бројеве, и прави Милер–Рабин приказ за бројеве величине какви се користе у криптографији.
🔒 У потпуности се обрађује у вашем претраживачу — ништа што овде унесете се никада не отпрема.
Резултат
Провера прималности вам говори да ли је цео број прост, и — за разлику од већине калкулатора на мрежи — показује вам стварни алгоритам којим је то доказано, а не кеширану табелу. Унесите било који цео број, позитиван или негативан, мали или огроман, и алатка на основу његове величине одлучује који од правих алгоритама да примени.
За бројеве испод 10¹² (један билион), извршава се право пробно дељење: почевши од 2, испробава се сваки целобројни кандидат до највећег целог броја који није већи од √n као могући делилац, заустављајући се чим неки дели без остатка (сложен) или потврђујући да ниједан не дели када се провери сваки кандидат до √n (прост). За огроман број кандидата приказани траг је ограничен на првих ~18 испробаних плус последњи, уз поштену напомену колико их је прескочено у приказу — али сваки појединачни кандидат се и даље стварно проверава у коду, ниједан није прескочен у израчунавању.
За бројеве на тој граници или изнад ње — опсег величина који се користи у криптографији — пробно дељење би трајало предуго, па алатка прелази на Милер–Рабинов тест прималности са фиксним, детерминистичким скупом од 13 простих сведока (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Тај тачно одређени скуп сведока је добро познат резултат: нема лажних позитивних ни за једно n испод 3.317.044.064.679.887.385.961.981 (око 3,3×10²⁴), што је граница утврђена рачунском провером (видети Sorenson & Webster, 2015, и широко репродуковану табелу детерминистичких сведока којој припада). Изнад те границе исти тест се и даље извршава, али вам алатка искрено каже да гаранција постаје изузетно снажна вероватноћа, а не математичка сигурност.
Милер–Рабинов траг записује n − 1 = 2ˢ × d са непарним d, затим пролази кроз право BigInt модуларно степеновање — квадрирај-и-множи, сводећи по модулу n на сваком кораку тако да бројеви никада не експлодирају — бит по бит за првог сведока, и извештава о пресуди сваког сведока, укључујући који сведок доказује сложеност ако се испостави да број није прост. Све ради локално у вашем прегледачу: нема сервера, нема спољног API-ја, никакви подаци не напуштају ваш уређај.