Test prvočíselnosti
Otestuje, zda je číslo prvočíslem, a přesně ukáže proč: u malých a středních čísel skutečné dělení postupných dělitelů až do √n, u kryptograficky velkých čísel poctivý rozfázovaný průchod Millerovým–Rabinovým testem.
🔒 Zpracováno výhradně ve vašem prohlížeči – nic, co zde zadáte, se nikdy nenahraje.
Výsledek
Test prvočíselnosti vám řekne, jestli je celé číslo prvočíslem, a na rozdíl od většiny kalkulaček na internetu vám ukáže konkrétní algoritmus, který to prokázal, ne žádnou předem uloženou vyhledávací tabulku. Zadejte libovolné celé číslo, kladné nebo záporné, malé nebo obrovské, a nástroj sám podle jeho velikosti rozhodne, který algoritmus použije.
U čísel menších než 10¹² (jeden bilion) probíhá skutečné dělení postupných dělitelů: počínaje dvojkou se postupně testují všechna celá čísla jako možní dělitelé až do dolní celé části √n, testování se zastaví ve chvíli, kdy je nalezen dělitel (složené číslo), nebo se potvrdí prvočíselnost, jakmile jsou prověřeni všichni kandidáti až do √n. Při velkém množství kandidátů se v zobrazené stopě ukáže prvních přibližně 18 vyzkoušených plus poslední, s poctivou poznámkou, kolik jich bylo ve výpisu přeskočeno — výpočet samotný ale ověřuje každého jednoho kandidáta, žádný se nepřeskakuje.
Pro čísla rovná tomuto prahu nebo větší — rozsah používaný v kryptografii — by dělení postupných dělitelů trvalo příliš dlouho, a proto nástroj přepíná na Millerův–Rabinův test prvočíselnosti s pevnou, deterministickou sadou 13 prvočíselných testovacích čísel (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41). Tato konkrétní sada je dobře známý výsledek: nedává falešně pozitivní výsledky pro žádné n menší než 3 317 044 064 679 887 385 961 981 (přibližně 3,3×10²⁴), což je mez prokázaná výpočetním ověřením (viz Sorenson & Webster, 2015, a příslušná široce používaná tabulka deterministických testovacích čísel). Nad touto mezí test probíhá stejným způsobem, ale nástroj poctivě uvádí, že záruka se mění na extrémně silnou pravděpodobnostní, nikoli matematickou jistotu.
Stopa Millerova–Rabinova testu zapíše n − 1 = 2ˢ × d s d lichým, a poté prochází reálné modulární umocňování BigInt — square-and-multiply, s redukcí modulo n v každém jednotlivém kroku, aby čísla nikdy neexplodovala — bit po bitu pro první testovací číslo, a u každého testovacího čísla oznamuje výsledek, včetně toho, které testovací číslo prokazuje složenost, pokud se ukáže, že číslo není prvočíslem. Vše běží lokálně ve vašem prohlížeči: žádný server, žádné externí API, žádná data neopouští vaše zařízení.