Тест Миллера (теория чисел)

У этого термина существуют и другие значения, см. Тест Миллера.

Не следует путать с «Тестом Миллера — Рабина» — вероятностным полиномиальным тестом простоты.

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

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

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

Свойства

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

Примечания

1. ↑ Miller, Gary L. Riemann's hypothesis and tests for primality // Journal of Computer and System Sciences. — 1976. — В. 3. — Т. 13. — С. 300—317. — ISSN 0022-0000. — DOI:10.1016/S0022-0000(76)80043-8
2. ↑ Bach, Eric Analytic methods in the analysis and design of number-theoretic algorithms. — Cambridge, MA: MIT Press, 1985. — 48 с. — ISBN 978-0-262-02219-4
3. ↑ Владимиров С. М. Некоторые изменения алгоритма Миллера (рус.) // Труды 48 конференции МФТИ. Секция радиотехники и защиты информации. — Долгопрудный: МФТИ, 2006.

Ссылки

• Miller, Gary L. Riemann's hypothesis and tests for primality // Journal of Computer and System Sciences. — 1976. — В. 3. — Т. 13. — С. 300—317. — ISSN 0022-0000. — DOI:10.1016/S0022-0000(76)80043-8
• Weisstein, Eric W. Miller's Primality Test (англ.) на сайте Wolfram MathWorld.