Перевірка числа на простоту
Перевірте, чи є число простим, і побачте чому: справжнє пробне ділення до √n для малих і середніх чисел та справжній покроковий тест Міллера — Рабіна для криптографічно великих чисел.
Результат
Перевірка на простоту повідомляє, чи є ціле число простим, і, на відміну від більшості онлайн-калькуляторів, показує справжній алгоритм, який це довів, а не значення з готової таблиці. Введіть будь-яке ціле число — додатне чи від'ємне, маленьке чи величезне — і інструмент сам обирає, який реальний алгоритм застосувати, залежно від розміру числа.
Для чисел, менших за 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, жодні дані ніколи не залишають ваш пристрій.
Дані не залишають ваш пристрій. Конвертація відбувається на клієнті в межах браузера. Безпека гарантована.
Нюанси та Формати
- Слід пробного ділення: кандидати від 2 до √n, дільник, що доводить складеність, або чесний доказ простоти «√n перевірено, дільника не знайдено».
- Детермінований тест Міллера — Рабіна з першими 13 простими свідками (від 2 до 41) — доведено коректний для чисел, менших за 3 317 044 064 679 887 385 961 981 (≈3,3×10²⁴).
- Справжній слід модульного піднесення до степеня BigInt методом «піднесення в квадрат і множення», побітово, щоб побачити, як насправді обчислюється a^d mod n.
Наші переваги
Сценарії використання
- • Перевірте простоту числа для домашнього завдання з дискретної математики чи інформатики, бачачи реальні кроки пробного ділення чи тесту Міллера–Рабіна, а не просто відповідь так/ні.
- • Перевірте велике кандидатне просте число, вивчаючи, як RSA та інші криптосистеми покладаються на справжній алгоритм Міллера–Рабіна, з покроково простеженим модульним піднесенням до степеня.
- • Швидко підтвердіть, чи є простим конкретне число, що постійно з'являється в задачі чи наборі вправ, перш ніж будувати на цьому припущенні подальшу логіку.
Оцініть інструмент
