Проверка на първичността

Проверката за основност ви казва дали дадено цяло число е просто и — за разлика от повечето онлайн калкулатори — ви показва действителния алгоритъм, който го е доказал, а не кеширана справочна таблица. Въведете произволно цяло число, положително или отрицателно, малко или огромно, и инструментът решава кой реален алгоритъм да изпълни въз основа на неговия размер.

За числа под 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²4), граница, установена чрез изчислителна проверка (вижте Sorenson & Webster, 2015 и широко разпространената детерминистична таблица за свидетели принадлежи на). Над тази граница същият тест все още се изпълнява, но инструментът ви казва честно, че гаранцията става по-скоро изключително силна вероятностна, отколкото математическа сигурност.

Проследяването на Милър–Рабин записва n − 1 = 2ˢ × d с d нечетно, след което преминава през истинско модулно степенуване на BigInt — квадрат и умножение, намалявайки модул n на всяка отделна стъпка, така че числата никога да не експлодират — малко по малко за първия свидетел, и докладва присъдата на всеки свидетел, включително кой свидетел доказва съставността, ако числото се окаже, че не е просто. Всичко работи локално във вашия браузър: няма сървър, няма външен API, никакви данни не напускат вашето устройство.