Проверка за простота
Проверете дали дадено число е просто и вижте точно защо: истинско деление на кандидати до √n за малки и средни числа и автентична демонстрация на Miller–Rabin стъпка по стъпка за числа с криптографски размери.
🔒 Обработва се изцяло във вашия браузър - нищо, което въвеждате тук, никога не се качва.
Резултат
Инструментът за проверка на простота ви казва дали дадено цяло число е просто и — за разлика от повечето онлайн калкулатори — ви показва реалния алгоритъм, който го е доказал, а не кеширана справочна таблица. Въведете произволно цяло число, положително или отрицателно, малко или огромно, и инструментът сам решава кой истински алгоритъм да използва според размера му.
За числа под 10¹² (един трилион) се извършва истинско деление на кандидати: започвайки от 2, се изпробва всяко цяло число до долната цяла част на √n като потенциален делител, като процесът спира в момента, в който някое раздели без остатък (съставно), или потвърждава, че няма такова, след като всеки кандидат до √n е бил проверен (просто). При огромен брой кандидати показаното проследяване се ограничава до първите ~18 изпробвани плюс последния, с честна бележка колко са пропуснати във визуализацията — но всеки един кандидат все пак реално се проверява от кода, нито един не се пропуска в изчисленията.
За числа на или над този праг — размерният диапазон, използван в криптографията — делението на кандидати би отнело твърде много време, затова инструментът превключва на теста за простота на Miller–Rabin с фиксиран, детерминистичен набор от 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, и широко възпроизвежданата таблица с детерминистични свидетели, към която принадлежи). Над тази граница тестът пак се изпълнява, но инструментът честно ви казва, че гаранцията става изключително силна вероятностна, а не математическа сигурност.
Проследяването на Miller–Rabin записва n − 1 = 2ˢ × d с нечетно d, след което преминава през истинско модулно степенуване с BigInt — умножение и повдигане на квадрат (square-and-multiply), с редукция по модул n на всяка отделна стъпка, за да не нарастват числата неконтролируемо — бит по бит за първия свидетел, и докладва решението на всеки свидетел, включително кой свидетел доказва съставност, ако числото се окаже, че не е просто. Всичко работи локално във вашия браузър: без сървър, без външен API, никакви данни не напускат устройството ви.