WikiSort.ru - Не сортированное

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

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

Ввод: 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-функциями Дирихле). ^[2].

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

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

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 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.

Для улучшения этой статьи желательно: Добавить иллюстрации. Проставив сноски, внести более точные указания на источники.