Калькулятор тесту простоти Міллера–Рабіна

Про цей калькулятор

Тест Міллера–Рабіна перевіряє простоту числа, записуючи n − 1 як 2ˢ·d з непарним d, а потім перевіряючи, чи свідок a задовольняє aᵈ ≡ 1 (mod n) або a^(2ʳ·d) ≡ −1 (mod n) для деякого r < s. Один свідок дає лише ймовірнісний результат, але перевірка за невеликим доведеним набором фіксованих основ-свідків (наприклад, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) робить тест детермінованим для кожного цілого числа менше приблизно 3,18 × 10²³ — це набагато більше, ніж потрібно більшості застосунків.

Криптографи та розробники програмного забезпечення використовують саме такий тест під час генерації великих кандидатів у прості числа для ключів RSA чи Діффі–Геллмана, а студенти-інформатики — щоб побачити на реальних числах, чому тест Міллера–Рабіна масштабується значно краще, ніж перебір дільників, для перевірки простоти великого цілого числа.