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

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

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

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

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

Алгоритм

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

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

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

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

Первоначально тот же результат был доказан для $70\cdot ln^{2}(n)$ , но впоследствии в 1985 году Эрик Бах^[англ.] уменьшил ^[3] коэффициент до 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 < 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 включительно;
число $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))$ ^[4] , но при этом алгоритм опирается на обобщённую гипотезу Римана. Проще говоря, трудоёмкость алгоритма растёт быстрее чем $O(ln^{2}(n))$ , (количество проверяемых оснований на псевдопростоту), потому что чем больше основание, тем более трудоёмкий его анализ. От размера (меры) входных данных: длины записи $m$ , проверяемого числа $n$ , трудоёмкость алгоритма значит, зависит так: $O(m^{4})$ , то есть полиномиальная сложность, 4-й степени.

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

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

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

Это только один из примеров, и переменную maxChecked, можно определить по другому, и по формуле $2\cdot ln^{2}(n)$ от проверяемого числа (классический тест Миллера), и по точным значениям для чисел, меньших чем $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, 1976, pp.300-317
↑ Ankeny N. C, 1952, pp.65-72
↑ Bach, Eric, 1985
↑ ¹ ² Василенко О. Н, 2003, pp.32—37

Литература

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.
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. Analytic methods in the analysis and design of number-theoretic algorithms. — Cambridge, MA: MIT Press, 1985. — 48 с. — ISBN 978-0-262-02219-4.
Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — МЦНМО. — 2003. — ISBN 5-94057_103_4.

[1] Miller, Gary L, 1976, pp.300-317

[2] Ankeny N. C, 1952, pp.65-72

[3] Bach, Eric, 1985

[Василенко-4] ¹ ² Василенко О. Н, 2003, pp.32—37

[1]

[2]

[3]

[4]

Теоретико-числовые алгоритмы
Тесты простоты	Миллера Миллера — Рабина Люка — Лемера Пепина Агравала — Каяла — Саксены Соловея — Штрассена
Поиск простых чисел	Перебор делителей Решето Эратосфена Решето Аткина Решето Сундарама
Факторизация	Перебор делителей Метод Ферма p−1-метод Полларда ρ-алгоритм Полларда Метод Лемана Метод эллиптических кривых (алгоритм Ленстры) Алгоритм Диксона Квадратичное решето
Дискретное логарифмирование	Алгоритм Гельфонда — Шенкса Алгоритм Полига — Хеллмана ρ-метод Полларда Алгоритм «кенгуру» Полларда Алгоритм Адлемана Алгоритм COS
Нахождение НОД	Алгоритм Евклида Расширенный алгоритм Бинарный алгоритм
Арифметика по модулю	Алгоритм Монтгомери Китайская теорема об остатках
Умножение и деление чисел	Алгоритм Карацубы Алгоритм Тоома — Кука Алгоритм Шёнхаге — Штрассена Алгоритм Фюрера Алгоритм Харви — ван дер Хувена Алгоритм Бурникеля — Циглера
Вычисление квадратного корня	Алгоритм Тонелли — Шенкса Алгоритм Берлекэмпа — Рабина