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

Тест Міллера — детермінований поліноміальний тест простоти, запропонований Міллером і вперше опублікований в 1976 році.

Опис алгоритму

Принцип роботи

Тест Міллера базується на тому, що непарне складене число $n$ або є степенем деякого простого числа, або існує просте число, яке належить інтервалу від $2$ до деякої функції $f(n)$, залежної від $n$, що не є свідком простоти даного числа по Міллеру.

Історія і модифікації

Даний тест простоти був запропонований Гарі Міллером в 1976 році та вперше був опублікований в журналі «Journal of Computer and System Sciences». Він базується на роботі Енкені про знаходження найменшого лишку, що ґрунтується на узагальнену гіпотезу Рімана (для узагальнень дзета-функцій, які мають назву L-функції Діріхле).

У припущенні справедливості узагальненої гіпотези Рімана, наразі (2016 рік) доведено, що як функції $f(n)$ можна взяти $2\cdot \ln ^{2}(n)$. Тобто для числа $n$, яке перевіряємо на простоту, необхідно перевірити, що воно сильно псевдопросте за всіма простим основами, меншими, $2\cdot \ln ^{2}(n)$, у такому випадку, число $n$ — просте, якщо вірна також, узагальнена гіпотеза Рімана.

Спочатку той же результат було доведено для $70\cdot \ln ^{2}(n)$, але пізніше у 1985 році Ерік Бах зменшив коефіцієнт до 2.

Однак, навіть якщо використовувати функцію $2\cdot \ln ^{2}(n)$, алгоритм Міллера працює набагато повільніше, ніж ймовірнісний алгоритм Міллера-Рабіна. Єдина перевага цього алгоритму (Міллера), що він достовірно встановлює простоту числа, спираючись лише на узагальнену гіпотезу Рімана. Ця гіпотеза досі не доведена, але є велика ймовірність і багато чисельних доказів на користь того, що вона вірна.

Існує також, ще більш посилена гіпотеза, на користь якої свідчать деякі теореми, і наближені оцінки. Порядок верхньої оцінки, був пізніше, запропонований Альфордом, Гранвіллем), Померанцем.

Якщо число $n$, сильно псевдопросте за всіма простими основами, меншими від $(\ln(n)\ln \ln(n))/\ln 2$, то число $n$ — просте. Однак, ця гіпотеза наразі (2016 рік), не доведена навіть у припущені узагальненої гіпотези Рімана. Можливо, пізніше, коли буде доведена узагальнена гіпотеза Рімана, і цей, ще сильніший результат, тоді алгоритм, який перевіряє простоту числа за цією умовою, і буде найшвидший доведений, достовірним алгоритмом перевірки числа на простоту. Насправді, щоб перевірити, наприклад, $1024$-бітне число на простоту (тобто, $n=2^{1024}$), треба лише переконатися, що воно сильно псевдопросте за всіма простими основами, меншими від $6722$, що зовсім небагато, у порівнянні з оцінкою $2\cdot \ln ^{2}(n)$, в алгоритмі Міллера: ми б перевіряли по всім простим основам до $1007582$. Алгоритм має поліноміальну трудомісткість, оскільки при зростанні розміру (міри) вхідних даних: довжини записів $m$, числа, що перевіряється (в будь-якій системі числення), обчислювана трудомісткість зростає, зі швидкістю зростання полінома якоїсь степені від $m$. (У випадку перевірки на простоту — алгоритми приймають тільки число, і розміром вхідних даних, саме число бути не може: розміром даних є саме довжина запису в якійсь системі числення).

Алгоритм Міллера, що перевіряє по всім простим основам, меншим ніж $(\ln(n)\ln \ln(n))/2$, працює вже ненабагато повільніше ймовірнісного алгоритму Міллера-Рабіна, (тобто його цілком практично можна використовувати), зате в порівнянні з ним має, явну перевагу. Алгоритм Міллера-Рабіна — завжди явно ймовірнісний, тобто ніколи неможна буде дізнатися достовірно що будь-яке отримане ним число — просте. А даний алгоритм скоріш за все — достовірний, тільки це ще потрібно довести. (І навіть якщо виявиться, що узагальнена гіпотеза Рімана невірна, тоді і алгоритм Міллера буде ймовірнісним, але він визначить прості числа, з великою ймовірністю, ніж реалізації алгоритму Міллера-Рабіна. Тому що ймовірнісний алгоритм Міллера-Рабіна запропонований, по суті, як спрощений варіант алгоритму Міллера, з метою підвищення швидкості обчислення). Знаходження саме достовірного, і разом з тим, самого швидкого алгоритму для визначення довільних простих чисел, може бути корисно в математичних теоріях, в яких досліджуються істинно прості числа, а не ймовірнісні.

Вищеописані умови перевірки визначені для скільки завгодно великих простих чисел, а для фіксованих чисел, відомі (на 2016 рік), результати, за якими числа $n\leq 10^{36}$ можна перевіряти на простоту, ще швидше. Ось, наприклад, деякі з них (для них використовується той самий класичний алгоритм Міллера, але з дуже малою кількістю основ).

• Число n < 2,047 просте, якщо воно сильно псевдопросте за основою a = 2;
• Число n < 1,373,653 просте, якщо воно сильно псевдопросте за основами a = 2, 3;
• Число n < 25,326,001 просте, якщо воно сильно псевдопросте за основами a = 2, 3, 5;
• Число n < 3,215,031,751 просте, якщо воно сильно псевдопросте за основами a = 2, 3, 5, 7;
• Число n < 2,152,302,898,747, просте, якщо воно сильно псевдопросте за основами a = 2, 3, 5, 7, 11;
• Число n < 3,474,749,660,383, просте, якщо воно сильно псевдопросте за основами a = 2, 3, 5, 7, 11, 13;
• Число n < 341,550,071,728,321, просте, якщо воно сильно псевдопросте за основами a = 2, 3, 5, 7, 11, 13, 17;
• Число n < 3,825,123,056,546,413,051, просте, якщо воно сильно псевдопросте за основами a = 2, 3, 5, 7, 11, 13, 17, 19, 23;
• Число n < 318,665,857,834,031,151,167,461, просте, якщо воно сильно псевдопросте за основами a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37;
• Число n < 3,317,044,064,679,887,385,961,981, просте, якщо воно сильно псевдопросте за основами a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41;
• …
• Число n < 1,543,267,864,443,420,616,877,677,640,751,301, просте, якщо воно сильно псевдопросте за основами від 2 до 61 включно;
• Число, просте, якщо воно сильно псевдопросте за основами від 2 до 71 включно.

Перше складене число $n$, яке є сильно псевдопростим за всіма простими основами до 71 включно, поки не знайдено, але відомо, що $n>10^{36}$.

Тобто, відомо (2016 рік), що всі числа, менші ніж $10^{36}$, які є сильно псевдопростими за першими 20 основами (до 71 включно), є також простими.

З цих даних бачимо, що перші $10^{36}$ натуральних чисел, можна перевірити на простоту (причому, достовірно, оскільки це вже доведено), використовуючи кількість основ, навіть менше ніж у всіх вище отриманих оцінках. Цей алгоритм — найшвидший для перевірки чисел на простоту.

Зворотне твердження таке: якщо число просте, то воно сильно псевдопросте, взагалі за всіма основами.

Також є версія алгоритму, яка не використовує розширену гіпотезу Рімана. Цей алгоритм має експоненційну обчислювальну складність. У цьому випадку в якості функції $f(n)$ виступає функція $c\cdot n^{\tfrac {1}{1+4{\sqrt {e}}}}\approx c\cdot n^{0{,}133}$.

Властивості

• Детермінізм: Тест є детермінований, тобто для одного й того ж n результат завжди буде один і той самий. Цим він відрізняється, наприклад, від своєї модифікації, теста Міллера — Рабіна, який є ймовірнісним.
• Поліноміальність: Час виконання тесту не більше ніж поліноміально залежить від бітової довжини числа n, що вигідно відрізняє його від повного перебору, теста Ферма или решета Ератосфена. Тим не менш швидкість виконання тесту на порядки повільніше, ніж у теста Міллера — Рабіна.
• Умовність: В основній версії алгоритму тест базується на недоведені розширеній гіпотезі Рімана, тобто є умовним. Цей тест відрізняється від тесту Агравал — Кайал — Саксена, який повністю доведений (і також є детермінованим і поліноміальним). Також є безумовна версія алгоритму, але вона працює дуже повільно, ніж основна.

Час роботи

У випадку, коли верхня межа перебору задається функцією $f(n)=2\cdot \ln ^{2}(n)$, то алгоритм детерміновано перевіряє простоту числа n за $O(\ln ^{4}(n))$, але при цьому алгоритм спирається на узагальнену гіпотезу Рімана. Простіше кажучи, трудомісткість алгоритму зростає швидше ніж $O(\ln ^{2}(n))$, (кількість основ, що перевіряється на псевдопростоту), тому що чим більша основа, тим більш трудомісткий його аналіз. Від розміру вхідних даних: довжини запису $m$, числа, що перевіряється $n$, тродоємність алгоритму значить, залежить так: $O(m^{4})$, тобто поліноміальна складність, 4-го ступеня.

У випадку, коли $f(n)=n^{0.133}$, час роботи в гіршому випадку оцінюється як $O(n^{1/7})$. Від розміру вхідних даних: довжини запису $m$, числа, що перевіряється $n$, тродомісткість алгоритму значить, залежить так: $O(e^{m/7})$, тобто експоненційна складність степені 1/7. Цей алгоритм набагато складніший: всі експоненційні алгоритми, при достатньо великому розмірі вхідних даних, стають істотно більш трудомісткими, ніж всі поліноміальні алгоритми.

Література

1. Miller, Gary L. Riemann's hypothesis and tests for primality // Journal of Computer and System Sciences. — 1976. — Т. 13, вып. 3. — ISSN 0022-0000. — DOI:10.1016/S0022-0000(76)80043-8.
2. Ankeny N. C. The least quadratic non-residue // Annals of Mathematics. — 1952. — Т. 55.
3. H. Cohen, H. W. Lenstra, Jr. Primality Testing and Jacobi Sums // Mathematics of Computation. — 1984. — Т. 42, вып. 165.
4. 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.
5. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — МЦНМО. — 2003. — ISBN 5-94057_103_4.