Kontrola primality

Kontrola primality vám řekne, zda je celé číslo prvočíslo, a – na rozdíl od většiny online kalkulaček – vám ukáže skutečný algoritmus, který to dokázal, nikoli vyhledávací tabulku uloženou v mezipaměti. Zadejte libovolné celé číslo, kladné nebo záporné, malé nebo obrovské, a nástroj rozhodne, který skutečný algoritmus bude spuštěn na základě jeho velikosti.

Pro čísla menší než 10¹² (jeden bilion) spustí skutečné zkušební dělení: počínaje 2 zkouší každého kandidáta na celé číslo až do dna √n jako možného dělitele, zastaví se v okamžiku, kdy se dělí rovnoměrně (složené), nebo potvrdí žádné, jakmile je každý kandidát do √n zkontrolován (prvočíslo). Pro velký počet kandidátů je zobrazená stopa omezena na prvních ~18 pokusů plus poslední, s upřímnou poznámkou o tom, kolik jich bylo na displeji přeskočeno – ale každý jednotlivý kandidát je stále skutečně kontrolován kódem, žádný není při výpočtu přeskočen.

Pro čísla na tomto prahu nebo nad ním – rozsah velikostí používaný v kryptografii – by zkušební dělení trvalo příliš dlouho, takže nástroj přejde na Miller-Rabinův test primality s pevnou, deterministickou sadou 13 hlavních svědků (2, 3, 5, 7, 11, 13, 17, 19, 23, 237, 31, 11,). Tato přesná množina svědků je dobře známým výsledkem: nemá žádné falešně pozitivní výsledky pro žádné n pod 3 317 044 064 679 887 385 961 981 (přibližně 3,3 × 10²⁴), což je hranice stanovená výpočetní verifikací (viz Sorenson & Webster, tabulka široce reprodukovaná determinovanost a reprodukovatelnost, 2015, Nad touto hranicí stále běží stejný test, ale nástroj vám upřímně řekne, že záruka se stává extrémně silnou pravděpodobnostní spíše než matematickou jistotou.

Miller-Rabinova stopa zapisuje n − 1 = 2ˢ × d s d lichým, pak prochází skutečnou modulární umocňováním BigInt – čtvercem a násobením, snižuje modulo n v každém jednotlivém kroku, takže čísla nikdy nevybuchnou – kousek po kousku pro prvního svědka, a oznámí verdikt každého svědka, včetně toho, které číslo se ukáže jako nesložené. Vše běží lokálně ve vašem prohlížeči: žádný server, žádné externí API, žádná data nikdy neopustí vaše zařízení.