Прималити Цхецкер

Провера примарности вам говори да ли је цео број прост, и – за разлику од већине калкулатора на мрежи – показује стварни алгоритам који је то доказао, а не кеширану табелу претраживања. Откуцајте било који цео број, позитиван или негативан, мали или огроман, а алат одлучује који ће прави алгоритам покренути на основу његове величине.

За бројеве испод 10¹² (један трилион), покреће право пробно дељење: почевши од 2, покушава сваки целобројни кандидат до пода од √н као могући делилац, заустављајући се у тренутку када се дели равномерно (композит) или потврђује да ниједан не чини када се провери сваки кандидат до √н (приме). За велики број кандидата, приказани траг је ограничен на првих ~18 покушаја плус последњи, са искреном напоменом о томе колико их је прескочено на екрану — али сваки појединачни кандидат се и даље проверава кодом, ниједан није прескочен у прорачуну.

За бројеве на или изнад тог прага — опсега величине који се користи у криптографији — пробно дељење би трајало предуго, тако да се алатка пребацује на Милер-Рабин тест примарности са фиксним, детерминистичким скупом од 13 основних сведока (2, 3, 5, 7, 11, 13, 17, 19, 23, 14 12). Овај тачан скуп сведока је добро познат резултат: нема лажних позитивних резултата за било које н испод 3,317,044,064,679,887,385,961,981 (око 3,3×10²⁴), границу утврђену компјутерском верификацијом (видети Соренсон и Вебстер, поново утврдити табелу 201 широм света). припада). Изнад те границе исти тест и даље траје, али алатка вам искрено говори да гаранција постаје изузетно јака вероватноћа, а не математичка сигурност.

Миллер–Рабин траг записује н − 1 = 2ˢ × д са д непарним, а затим пролази кроз реалну БигИнт модуларну експоненцијалност — квадрат и множење, смањујући модул н на сваком кораку тако да бројеви никада не експлодирају — мало по мало за првог свједока, и извјештава о пресуди сваког свједока, укључујући и који број свједока доказује да је прост број несложен. Све ради локално у вашем претраживачу: ниједан сервер, нема спољни АПИ, ниједан податак никада не напушта ваш уређај.