Перевірка простоти

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

Для чисел менших за 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²⁴); ця межа встановлена обчислювальною перевіркою (див. Sorenson & Webster, 2015 та широко відтворювану таблицю детермінованих свідків, до якої вона належить). Понад цю межу той самий тест усе ще виконується, але інструмент чесно зазначає, що гарантія стає надзвичайно сильною ймовірнісною, а не математичною достовірністю.

Траса Міллера-Рабіна записує n − 1 = 2ˢ × d, де d непарне, потім покроково проходить справжнє модулярне експоненціювання BigInt — піднесення до квадрату та множення, зводячи за модулем n на кожному окремому кроці, щоб числа ніколи не вибухали — біт за бітом для першого свідка, і повідомляє вердикт для кожного свідка, включно з тим, який свідок доводить складеність, якщо виявиться, що число не просте. Усе виконується локально у вашому браузері: без сервера, без зовнішнього API, жодні дані ніколи не покидають ваш пристрій.