Тест Миллера

Тест Миллера — детерминированный полиномиальный тест простоты, предложенный Миллером и впервые опубликованный в 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 простых чисел p1,...,pm\texttt, где \textttm\texttt такое, что pmf(n)pm+1\\\texttt     Вычислить s\texttt и q\texttt такие, что n1=q2s\texttt и q\texttt - нечётное\\\texttt     Положить i=1\texttt \textttперейти на шаг\texttt (4)\\\texttt(3)  \textttесли\texttt im\texttt, \textttто\texttt i=i+1\texttt \\\texttt     \textttесли\texttt i>m\texttt, \textttто\texttt \textttвернуть\texttt \textttпростое\\\texttt(4)  \textttесли\texttt pi|n\texttt, \textttто\texttt \textttвернуть\texttt \textttсоставное\\\texttt     Вычислить piqmodn,piq2modn,...,piq2smodn\\\texttt(5)  \textttесли\texttt piq2smodn1\texttt \textttто\texttt \textttвернуть\texttt \textttсоставное\\\texttt(6)  \textttесли\texttt piqmodn=1\texttt \textttто\texttt \textttперейти на шаг\texttt (3)\\\texttt     Положить j=max(j:piq2jmodn1)\\\texttt(7)  \textttесли\texttt piq2jmodn=n1\texttt \textttто\texttt \textttперейти на шаг\texttt (3)\\\texttt(8)  \textttвернуть\texttt \textttсоставное

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


 Данный тест простоты был предложен Гари Миллером в 1976 году и впервые был опубликован в журнале "Journal of Computer and System Sciences". Он основывается на работе Анкени о нахождении наименьшего невычета, опирающейся на обобщенную гипотезу Римана (для обобщений дзета-функций, называемых L-функциями Дирихле). .
 В предположении справедливости обобщенной гипотезы Римана, на данный момент (2016 год), доказано, что в качестве функции f(n) можно взять 2ln2(n). То есть для проверяемого на простоту числа n нужно проверить, что оно сильно псевдопростое по всем простым основаниям, меньшим, 2ln2(n), в таком случае, число n - простое, если верна также обобщенная гипотеза Римана.
 Первоначально тот же результат был доказан для 70ln2(n), но впоследствии в 1985 году уменьшил
 коэффициент до 2.
 Однако, даже если использовать функцию 2ln2(n) , алгоритм Миллера работает на много порядков медленнее, чем вероятностный алгоритм Миллера-Рабина. Единственное преимущество этого алгоритма (Миллера), что он достоверно устанавливает простоту числа, опираясь лишь на обобщенную гипотезу Римана. А эта гипотеза хотя и не доказана до сих пор, но есть большая вероятность, а также много численных свидетельств в пользу того, что она верна.
 Существует также еще более усиленная гипотеза, в пользу которой свидетельствуют некоторые теоремы и эвристические оценки. Порядок верхней оценки был позже предложен , и Померансом.
Если число n, сильно псевдопростое по всем простым основаниям, меньшим чем (lnnlnlnn)/ln2 , то число n - простое. Однако, эта гипотеза на данный момент (2016 год) не доказана даже в предположении обобщенной гипотезы Римана. Возможно, позже, когда будет доказана обобщенная гипотеза Римана, и этот, еще более сильный результат, тогда алгоритм, проверяющий простоту числа по этому условию, и будет самым быстрым доказанным, достоверным алгоритмом проверки числа на простоту. В самом деле, чтобы проверить к примеру, 1024-битное число на простоту (то есть $n = 2^{1024$), нужно убедиться всего лишь, что оно сильно псевдопростое по всем простым основаниям, меньшим чем 6722 , что совсем немного, в сравнении с оценкой 2ln2(n), в алгоритме Миллера: мы бы проверяли по всем простым основаниям до 1007582 . Алгоритм имеет полиномиальную трудоемкость, так как при росте размера (меры) входных данных: длины записи m, проверяемого числа n (в любой системе счисления), вычислительная трудоемкость растет, со скоростью роста полинома некоторой степени от m. (В случае проверки на простоту или факторизации алгоритмы принимают только число, и размером входных данных, само число являться не может: размером данных является именно длина записи в какой то системе счисления).
 Алгоритм Миллера, проверяющий по всем простым основаниям, меньшим чем (lnnlnlnn)/ln2, работает уже ненамного медленнее вероятностного алгоритма Миллера-Рабина, (то есть его вполне практично можно использовать), зато имеет по сравнению с ним явное преимущество. Алгоритм Миллера-Рабина всегда явно вероятностный, то есть никогда нельзя будет узнать достоверно что любое полученное им число простое. А данный алгоритм, скорее всего, достоверный, только это еще нуждается в доказательстве. (И даже если окажется, что обобщенная гипотеза Римана неверна, и тогда алгоритм Миллера будет вероятностным, но он определит простоту числа, с большей вероятностью, чем реализации алгоритма Миллера-Рабина. Потому что вероятностный алгоритм Миллера-Рабина был предложен, по сути, как упрощенный вариант алгоритма Миллера с целью повышения скорости вычислений). Нахождение именно достоверного, и вместе с тем самого быстрого алгоритма для определения простоты произвольных чисел, может быть полезно в математических теориях, в которых исследуются истинно простые числа, а не вероятностные.
 Вышеописанные условия проверки определены для сколь угодно больших простых чисел, а для фиксированных чисел, известны (на 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) выступает функция cn11+4ecn0,133.

Свойства



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

Время работы


 В случае, когда верхняя граница перебора задаётся функцией f(n)=2ln2(n), алгоритм детерминировано проверяет простоту числа n за O(ln4(n))
 , но при этом алгоритм опирается на обобщенную гипотезу Римана. Проще говоря, трудоемкость алгоритма растет быстрее чем O(ln2(n)), (количество проверяемых оснований на псевдопростоту), потому что чем больше основание, тем более трудоемкий его анализ. От размера (меры) входных данных: длины записи m, проверяемого числа n , трудоёмкость алгоритма значит, зависит так: O(m4), то есть полиномиальная сложность, 4-й степени.
 В случае, когда f(n)=n0.133, время работы в худшем случае оценивается как O(n1/7) . От размера входных данных: длины записи m, проверяемого числа n, трудоёмкость алгоритма, зависит так: O(em/7), то есть экспоненциальная сложность степени 1/7. Этот алгоритм намного сложнее: все экспоненциальные алгоритмы, при достаточно большом размере входных данных, становятся существенно более трудоемкими, чем все полиномиальные алгоритмы.

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


 Пример реализации алгоритма, на языке программирования C\# (.NET Framework 3.5, 4.0).
 Это только один из примеров, и переменную maxChecked, можно определить по другому, и по формуле 2ln2(n) от проверяемого числа (классический тест Миллера), и по точным значениям для чисел, меньших чем $10^{36$, описанным выше, и вообще произвольным образом так, что получится реализация алгоритма Миллера-Рабина.
 \beginverbatim public 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.