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

Об этом калькуляторе

Тест Миллера — Рабина проверяет простоту, записывая 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 или Диффи — Хеллмана, а студенты, изучающие информатику, — чтобы на реальных числах увидеть, почему тест Миллера — Рабина масштабируется гораздо лучше, чем пробное деление, при проверке того, является ли большое целое число простым.