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

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

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

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

Алгоритм

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

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

Данный тест простоты был предложен Гари Миллером в 1976 году и впервые был опубликован в журнале " Journal of Computer and System Sciences ". Он основывается на работе Анкени о нахождении наименьшего невычета , опирающейся на обобщённую гипотезу Римана (для обобщений дзета-функций, называемых L-функциями Дирихле). .

В предположении справедливости обобщённой гипотезы Римана, на данный момент (2016 год), доказано, что в качестве функции ${\displaystyle f(n)}$ можно взять ${\displaystyle 2\cdot ln^{2}(n)}$ . То есть для проверяемого на простоту числа ${\displaystyle n}$ нужно проверить, что оно сильно псевдопростое по всем простым основаниям, меньшим, ${\displaystyle 2\cdot ln^{2}(n)}$ , в таком случае, число ${\displaystyle n}$ - простое, если верна также обобщённая гипотеза Римана.

Первоначально тот же результат был доказан для ${\displaystyle 70\cdot ln^{2}(n)}$ , но впоследствии в 1985 году уменьшил коэффициент до 2.

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

Существует также ещё более усиленная гипотеза, в пользу которой свидетельствуют некоторые теоремы и эвристические оценки. Порядок верхней оценки был позже предложен , и Померансом .

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

Алгоритм Миллера, проверяющий по всем простым основаниям, меньшим чем ${\displaystyle (\ln n\ln \ln n)/\ln 2}$ , работает уже ненамного медленнее вероятностного алгоритма Миллера-Рабина, (то есть его вполне практично можно использовать), зато имеет по сравнению с ним явное преимущество. Алгоритм Миллера-Рабина — всегда явно вероятностный, то есть никогда нельзя будет узнать достоверно что любое полученное им число — простое. А данный алгоритм, скорее всего, — достоверный, только это ещё нуждается в доказательстве. (И даже если окажется, что обобщённая гипотеза Римана неверна, и тогда алгоритм Миллера будет вероятностным, но он определит простоту числа, с большей вероятностью, чем реализации алгоритма Миллера-Рабина. Потому что вероятностный алгоритм Миллера-Рабина был предложен, по сути, как упрощённый вариант алгоритма Миллера с целью повышения скорости вычислений). Нахождение именно достоверного, и вместе с тем самого быстрого алгоритма для определения простоты произвольных чисел, может быть полезно в математических теориях, в которых исследуются истинно простые числа, а не вероятностные.

Вышеописанные условия проверки определены для сколь угодно больших простых чисел, а для фиксированных чисел, известны (на 2016 год), результаты, по которым числа

${\displaystyle n<=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 включительно;
• число ${\displaystyle n<=10^{36}}$ простое, если оно сильно псевдопростое по всем простым основаниям от 2 до 71 включительно.

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

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

Из этих данных видим, что первые ${\displaystyle 10^{36}}$ натуральных чисел, можно проверить на простоту ( причём, достоверно, так как это уже доказано ), используя количество оснований, даже меньше чем во всех выше полученных оценках. Этот алгоритм - самый быстрый для проверки чисел на простоту.

Обратное же утверждение следующее — если число простое, то оно сильно псевдопростое, вообще по всем основаниям.

Также есть версия алгоритма, не использующая расширенную гипотезу Римана. Этот алгоритм имеет экспоненциальную вычислительную сложность. В таком случае в роли функции ${\displaystyle f(n)}$ выступает функция ${\displaystyle c\cdot n^{\tfrac {1}{1+4{\sqrt {e}}}}\approx c\cdot n^{0{,}133}}$ .

Свойства

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

Время работы

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

В случае, когда ${\displaystyle f(n)=n^{0.133}}$ , время работы в худшем случае оценивается как ${\displaystyle O(n^{1/7})}$ . От размера входных данных: длины записи ${\displaystyle m}$ , проверяемого числа ${\displaystyle n}$ , трудоёмкость алгоритма, зависит так: ${\displaystyle O(e^{m/7})}$ , то есть экспоненциальная сложность степени 1/7. Этот алгоритм намного сложнее: все экспоненциальные алгоритмы, при достаточно большом размере входных данных, становятся существенно более трудоёмкими, чем все полиномиальные алгоритмы.

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

Пример реализации алгоритма, на языке программирования C# (.NET Framework 3.5, 4.0).

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

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 IsPowerOfNumber(BigInteger 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;
}

Остаётся реализовать только две функции -

1) NextPrime, которая получает число, и возвращает следующее за ним, простое число, оптимальная для нахождения именно малых простых чисел. Эта функция должна быть ещё проще и быстрее.

2) IsPowerOfNumber - функция, немного более сложная, которая определяет, является ли передаваемое число, степенью другого, простого числа. Нужно найти максимально простую реализацию этой функции.

Также,

3) Можно ускорить реализацию алгоритма , отсеяв вначале, случаи, когда число делится на возможные малые делители, но часто-встречающиеся делители: 2,3,5,7,11... и только потом выполнять основную проверку по алгоритму Миллера.

В таком случае реализация алгоритма Миллера в предложенном примере, скорее всего, будет наибыстрейшей, для произвольных больших чисел. А сам алгоритм, как уже показано выше, претендует на звание самого быстрого достоверного алгоритма на проверку простоты (если верна обобщённая гипотеза Римана).

Эта реализация алгоритма была успешно протестирована и без использования функции IsPowerOfNumber.

Примечания

Литература

• Miller, Gary L. Riemann's hypothesis and tests for primality // Journal of Computer and System Sciences. — 1976. — Т. 13 , вып. 3 . — ISSN . — doi : .
• Ankeny N. C. The least quadratic non-residue // Annals of Mathematics. — 1952. — Т. 55 .
• H. Cohen , H. W. Lenstra, Jr. Primality Testing and Jacobi Sums // Mathematics of Computation. — 1984. — Т. 42 , вып. 165 .
• Bach, Eric. . — Cambridge, MA: MIT Press, 1985. — 48 с. — ISBN 978-0-262-02219-4 .
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — МЦНМО. — 2003. — ISBN 5-94057_103_4.