Тест Миллера — детерминированный полиномиальный тест простоты.

В 1976 году Миллер показал,^[1] что если число a не является свидетелем простоты числа n (по Миллеру), то n является составным числом. Кроме того, в предположении расширенной гипотезы Римана, для составного числа n найдётся , которое не будет являться свидетелем простоты.

В 1985 году Бах снизил^[2] необходимую границу до , а в 2006 году Владимиров показал,^[3] что при последовательном проходе кандидатов a имеет смысл проверять только простые числа.

Свойства

• Тест является детерминированным, то есть для одного и того же n результат всегда будет один и тот же. Этим он отличается, например, от своей модификации, теста Миллера — Рабина, который является вероятностным.
• Время выполнения теста не более чем полиномиально зависит от битовой длины числа n, что выгодно отличает его от полного перебора, теста Ферма или решета Эратосфена. Тем не менее скорость выполнения теста на порядки медленнее, чем у теста Миллера — Рабина.
• Тест основывается на недоказанной расширенной гипотезе Римана. Этим тест отличается от теста Агравала — Каяла — Саксены, который полностью доказан (и также является детерминированным и полиномиальным).

Примечания