Тест Миллера

Тест Миллера — детерминированный полиномиальный тестпростоты, предложенный Миллером и впервые опубликованный в 1976 году .

Описаниеалгоритма


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


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

Алгоритм


\textttВвод\texttt: \textttn\texttt \textgreater 2, нечётное натуральное число, которое необходимо проверить на простоту;\\\textttВывод\texttt: \textttсоставное\texttt, означает, что \textttn\texttt является составным числом;\\\texttt       \textttпростое\texttt, означает, что \textttn\texttt является простым числом.\\\texttt(1)  Проверить, является ли \textttn\texttt степенью какого-либо числа.\\\texttt     \textttесли\texttt является, \textttто\texttt \textttвернуть\texttt \textttсоставное\\\texttt(2)  Найти первые \textttm\texttt простых чисел $p_1, ..., p_m$\texttt, где \textttm\texttt такое, что $p_m \le f(n) \le p_{m+1}$\\\texttt     Вычислить $s$\texttt и $q$\texttt такие, что $n-1=q\cdot 2^s$\texttt и $q$\texttt - нечётное\\\texttt     Положить $i=1$\texttt \textttперейти на шаг\texttt (4)\\\texttt(3)  \textttесли\texttt $i\le m$\texttt, \textttто\texttt $i=i+1$\texttt \\\texttt     \textttесли\texttt $i> m$\texttt, \textttто\texttt \textttвернуть\texttt \textttпростое\\\texttt(4)  \textttесли\texttt $p_i|n$\texttt, \textttто\texttt \textttвернуть\texttt \textttсоставное\\\texttt     Вычислить $p_i^q \bmod n, p_i^{q\cdot 2}\bmod n, ..., p_i^{q\cdot 2^s}\bmod n$\\\texttt(5)  \textttесли\texttt $p_i^{q\cdot 2^s}\bmod n \ne 1$\texttt \textttто\texttt \textttвернуть\texttt \textttсоставное\\\texttt(6)  \textttесли\texttt $p_i^{q}\bmod n = 1$\texttt \textttто\texttt \textttперейти на шаг\texttt (3)\\\texttt     Положить $j = \max(j:p_i^{q \cdot 2^j}\bmod n \ne 1)$\\\texttt(7)  \textttесли\texttt $p_i^{q\cdot 2^j}\bmod n = n-1$\texttt \textttто\texttt \textttперейти на шаг\texttt (3)\\\texttt(8)  \textttвернуть\texttt \textttсоставное

История имодификации


 Данный тест простоты был предложен Гари Миллером в 1976 году и впервыебыл опубликован в журнале "Journal of Computer and SystemSciences". Он основывается на работе Анкени о нахождении наименьшегоневычета, опирающейся на обобщенную гипотезу Римана (для обобщенийдзета-функций, называемых 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$, проверяемого числа $n$ (в любой системесчисления), вычислительная трудоемкость растет, со скоростью ростаполинома некоторой степени от $m$. (В случае проверки напростоту или факторизации алгоритмы принимают только число, иразмером входных данных, само число являться не может: размером данныхявляется именно длина записи в какой то системе счисления).
 Алгоритм Миллера, проверяющий по всем простым основаниям, меньшим чем$(\ln n \ln \ln n) / \ln 2$, работает уже ненамного медленнеевероятностного алгоритма Миллера-Рабина, (то есть его вполне практичноможно использовать), зато имеет по сравнению с ним явное преимущество.Алгоритм Миллера-Рабина всегда явно вероятностный,то есть никогда нельзя будет узнать достоверно что любое полученное имчисло простое. А данный алгоритм, скорее всего, достоверный, только это еще нуждается в доказательстве. (И даже еслиокажется, что обобщенная гипотеза Римана неверна, и тогда алгоритмМиллера будет вероятностным, но он определит простоту числа, с большейвероятностью, чем реализации алгоритма Миллера-Рабина. Потому чтовероятностный алгоритм Миллера-Рабина был предложен, по сути, какупрощенный вариант алгоритма Миллера с целью повышения скоростивычислений). Нахождение именно достоверного, и вместе с тем самогобыстрого алгоритма для определения простоты произвольных чисел, можетбыть полезно в математических теориях, в которых исследуются истиннопростые числа, а не вероятностные.
 Вышеописанные условия проверки определены для сколь угодно большихпростых чисел, а для фиксированных чисел, известны (на 2016 год),результаты, по которым числа
$n <= 10^{36$ , можно проверять на простоту, ещебыстрее. Ниже в качестве примера даны некоторые из них (для нихиспользуем тот же классический алгоритм Миллера, но с очень малымколичеством оснований):

  • число n \textless 2 047 простое, если оно сильно псевдопростое по основаниям a = 2;
  • число n \textless 1 373 653 простое, если оно сильно псевдопростое по основаниям a = 2, 3;
  • число n \textless 25 326 001 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5;
  • число n \textless 3 215 031 751 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7;
  • число n \textless 2 152 302 898 747 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11;
  • число n \textless 3 474 749 660 383 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13;
  • число n \textless 341 550 071 728 321 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17;
  • число n \textless 3 825 123 056 546 413 051 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17, 19, 23;
  • число n \textless 318 665 857 834 031 151 167 461 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37;
  • число n \textless 3 317 044 064 679 887 385 961 981 простое, если оно сильно псевдопростое по основаниям a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41;
  • ...
  • число n \textless 1 543 267 864 443 420 616 877 677 640 751 301 простое, если оно сильно псевдопростое по всем простым основаниям от 2 до 61 включительно;
  • число $n <= 10^{36$ простое, если оно сильно псевдопростое по всем простым основаниям от 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. Этот алгоритм намного сложнее: все экспоненциальные алгоритмы, придостаточно большом размере входных данных, становятся существенно болеетрудоемкими, чем все полиномиальные алгоритмы.

Пример реализацииалгоритма.


 Пример реализации алгоритма, на языке программирования C\# (.NETFramework 3.5, 4.0).
 Это только один из примеров, и переменную maxChecked, можноопределить по другому, и по формуле $2\cdot ln^2(n)$ от проверяемогочисла (классический тест Миллера), и по точным значениям для чисел,меньших чем $10^{36$, описанным выше, и вообще произвольнымобразом так, что получится реализация алгоритма Миллера-Рабина.
 \beginverbatimpublic bool IsPrime_AlgMiller(BigInteger checkingNum) // (если является степенью другого числа) if (IsPowerOfNumber(checkingNum)) return false;
  BigInteger logN = new BigInteger(BigInteger.Log(checkingNum)); BigInteger loglogN = new BigInteger(BigInteger.Log(logN)); BigInteger maxChecked = logN * loglogN / (new BigInteger(BigInteger.Log(2)));
  // maxChecked: получено максимальное основание, для проверки на сильную псевддопростоту. Это один из примеров. BigInteger baseCurrent = new BigInteger(2);
  bool isPrime = true;
  while (baseCurrent <= maxChecked) // (если не сильно псевдопростое по этому основанию) if (! IsStrongPseudoPrime(checkingNum, baseCurrent)) // (тогда число не простое) isPrime = false; break;
  baseCurrent = NextPrime(baseCurrent);
  return isPrime;
 public bool IsStrongPseudoPrime(BigInteger checkingNum, BigInteger baseCurrent) BigInteger exp = checkingNum - 1;
  // (exp будет меняться, а проверка остатка -1 эквивалентна проверке остатка (checkingNum - 1)) BigInteger ost_1 = exp;
  BigInteger res = BigInteger.ModPow(baseCurrent, exp, checkingNum);
  if (res != 1) return false;
  // (тест Ферма пройден)
  while (true) // (четное; при первом попадании всегда будет четным, далее цикл до тех пор пока снова станет нечетным) exp = exp / 2;
  // (остаток -1 всегда должны проверить) res = BigInteger.ModPow(baseCurrent, exp, checkingNum);
  if (res == ost_1) return true;
  // (снова стало нечетным — нужно проверить еще на 1) if (!exp.IsEven) res = BigInteger.ModPow(baseCurrent, exp, checkingNum); if (res.IsOne) return true;
  break;
  return false;
 public BigInteger NextPrime(BigInteger num) //...
 public bool IsPowerOfNumberBigInteger n)// n=p^k => p-1|n-1 && 2^(p-1)=1(mod p) => 2^(n-1)=1(mod p) => p|2^(n-1)-1 => p|gcd(2^(n-1)-1,n) return BigInteger.GreatestCommonDivisor(BigInteger.ModPow(2, n - 1, n)-1, n)>1;\endverbatim
 Остается реализовать только две функции -
 1) NextPrime, которая получает число, и возвращает следующее заним, простое число, оптимальная для нахождения именно малых простыхчисел. Эта функция должна быть еще проще и быстрее.
 2) IsPowerOfNumber - функция, немного более сложная, котораяопределяет, является ли передаваемое число, степенью другого, простогочисла. Нужно найти максимально простую реализацию этой функции.
 Также,
 3) Можно ускорить реализацию алгоритма, отсеяв вначале, случаи,когда число делится на возможные малые делители, но часто-встречающиесяделители: 2,3,5,7,11... и только потом выполнять основную проверку поалгоритму Миллера.
 В таком случае реализация алгоритма Миллера в предложенном примере,скорее всего, будет наибыстрейшей, для произвольных больших чисел. А самалгоритм, как уже показано выше, претендует на звание самого быстрогодостоверного алгоритма на проверку простоты (если верна обобщеннаягипотеза Римана).
 Эта реализация алгоритма была успешно протестирована и без использованияфункции IsPowerOfNumber.