Тесты на простоту

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

Вероятностные тесты

Тест Ферма

Тест Ферма основывается на малой теореме Ферма, которая гласит

a \rprime p \implies a^{p-1} \equiv 1 \pmod p \quad\text{где}~ p ~\text{простое}

Чтобы узнать, является ли $n$ простым числом, нужно взять случайное число $a < n$ и проверить, выполняется ли $a^{n-1} \equiv 1 \pmod n$ . Число $a$ называется свидетелем простоты. Если равенство не выполняется, то с полной уверенностью можно сказать, что число составное. Если же $n$ прошло тест, то всё равно есть вероятность, что оно не простое.

Заметьте, что в малой теореме Ферма импликация идёт только в одну сторону: из взаимной простоты следует сравнение, но обратная импликация не всегда верна. Составные числа $n$ , удовлетворяющие сравнению $a^{n-1} \equiv 1 \pmod n$ для всех целых $a$ , взаимнопростых с $n$ , называются числами Кармайкла. Числа Кармайкла успешно проходят тест Ферма, хотя являются составными.

Давайте посмотрим на наименьшее число Кармайкла — $561 = 3 \cdot 11 \cdot 17$ . Из китайской теоремы об остатках следует, что $\ZZ_{561} = \ZZ_{3} \times \ZZ_{11} \times \ZZ_{17}$ . Возьмём $a$ взаимнопростое со всеми делителями $561$ , то есть

\align{ a \rprime 3 &\implies a^2 \eqmod{3} 1 \\ a \rprime 11 &\implies a^{10} \eqmod{11} 1 \\ a \rprime 17 &\implies a^{16} \eqmod{17} 1 }

$2$ , $10$ и $16$ являются делителями $560$ , значит $a^{560} \eqmod{561} 1$ .

Такие числа встречаются довольно редко, но их бесконечно много.

Вероятность ошибки одного теста будет $\varepsilon \le \varphi(n)/n$ . Выполнив тест Ферма $k$ раз, получим вероятность верного ответа $1 - \varepsilon^k$ .

function fermat_test(int n, int k) -> bool:
    for int i = 0; i < k; i++:
        select a = random uniform int [2, n-1]
        if pow(a, n-1) % n != 1:
            return false
    return true

Используя алгоритмы быстрого возведения в степень по модулю, можно получить время работы $O(k \log^2n \cdot \log \log n \cdot \log \log \log n)$ .

Тест Соловея-Штрассена

Тест Соловея-Штрассена предполагает проверку квадратичных вычетов, для этого нам понадобится критерий Эйлера.

Критерий Эйлера

$p$ — простое, $p > 2$ и $a \rprime p$

\align{&a^{(p-1)/2} \equiv 1 \pmod p ~ \text{когда} ~ a ~ \text{квадратичный вычет по модулю} ~ p \\ &a^{(p-1)/2} \equiv -1 \pmod p ~ \text{когда} ~ a ~ \text{квадратичный невычет}}

Рассмотрим три утверждения:

Существует такой $x$ , что $x^2 \equiv a \pmod p$
$a^{(p-1)/2} \equiv 1 \pmod p$
$a^{(p-1)/2} \equiv -1 \pmod p$

Из $p > 2$ следует, что $1 \notequiv p-1 \pmod p$ , а это то же самое, что $1 \notequiv -1 \pmod p$ , поэтому утверждения $2$ и $3$ не могут выполняться одновременно.

Пусть существует $x$ такое, что $x^2 \equiv a \pmod p$ . Возведём левую и правую часть в $(p-1)/2$ степень и получим $x^{p-1} \equiv a^{(p-1)/2} \pmod p$ . По малой теореме Ферма $x^{p-1} \equiv 1 \pmod p$ , а значит $a^{(p-1)/2} \equiv 1 \pmod p$ . Получается, что утверждения $1$ и $2$ всегда выполняются вместе.

Рассмотрим последовательность

1, \, 2, \, \dotsc, \, \frac{p-1}{2} , \, \frac{p+1}{2} , \, \dotsc , \ p-1

Из $-1 \equiv p-1 \pmod p$ следует

1^2 \equiv (p-1)^2, \, 2^2 \equiv (p-2)^2, \, \dotsc, \, \left( \frac{p-1}{2} \right)^2 \equiv \left( \frac{p+1}{2} \right)^2 \quad \pmod p

Получается, что сущетвует ровно $(p-1)/2$ квадратов по модулю $p$ . Обозначим их $a_1, \, a_2, \, \dotsm, \, a_{(p-1)/2}$ . Если $a$ равно $a_j$ , то сравнение $1$ имеет решение, а это значит, что и второе выполняется для любого $a_j$ . Следовательно, сравнение $2$ имеет ровно $(p-1)/2$ решений, отсюда же следует, что $3$ также имеет $(p-1)/2$ решений, при каждом из которых первое сравнение не выполняется.

Если число $n$ простое, то $n-1 = 2^s \cdot d$ , где $s$ целое, а $d$ нечётное. Очевидно, что ${\sqrt {a^{n-1}}} \eqmod{n} \pm 1$ . Значит, если мы возьмём случайное $a$ , то оно должно быть либо квадратичным вычетом, либо невычетом по модулю $n$ . Это можно выразить через символы Якоби следующим образом:

a^{n-1} \equiv 1 \quad \text{и} \quad a^{(n-1)/2} \equiv \legendre{a}{p} \pmod n

function solovay_strassen_test(int n, int k) -> bool:
    for int i = 0; i < k; i++:
        select a = random uniform int [2, n-1]
        if pow(a, (n-1)/2) % n != jacobi(a, p):
            return false
    return true

Асимптотическая сложность этого алгоритма равняется $O(k\log^3 n)$ , а вероятность ошибки $\varepsilon \le 1/2^k$ .

Тест Миллера-Рабина

Давайте усовершенствуем разобранные нами тесты. В предыдущем пункте мы выяснили, что $n-1=2^s \cdot d$ , значит мы можем брать корень из $a$ , пока не выполнится одно из двух:

a^d \equiv \pm 1 \quad \text{или} \quad a^{2^r \cdot d} \equiv -1 \quad \pmod n, ~ \text{где} ~ r < s

Если при взятии корня мы получили сравнимость по модулю $n$ с чем-то кроме $\pm 1$ , то число точно составное. Вероятность ошибки этого теста $\varepsilon \le 1/4$ . Значит, повторив тест Миллера-Рабина $k$ раз, мы получим вероятность верного ответа не меньше $1 - 1/4^k$ , что является очень хорошим результатом.

function miller_rabin_test(int n, int k) -> bool:
    for int i = 0; i < k; i++:
        select a = random uniform int [2, n-1]
        for int j = n-1; j % 2 == 0; j /= 2:
            if pow(a, j) % n == n-1:
                break
            else if pow(a, j) % n != 1:
                return false
    return true

Тест Миллера-Рабина способен определять некоторые числа Кармайкла, например, $561$ , но вот $1729$ , третье число Кармайкла, успешно проходит тест.

Сложность этого алгоритма составляет $O(k \log^3 n)$ .

Тест Фробениуса

Для использования теста Фробениуса нужно рассмотреть такое понятие как квадратичная иррациональность. Квадратичной иррациональностью будем называть число $z = a +b \sqrt c$ , где $a$ , $b$ и $c$ — целые и $c$ свободно от квадратов. Сопряжённым к $z$ будет $\bar{z} = a - b \sqrt c$ . А остаток от деления определим как $z \mod n = (a \mod n) + (b \mod n) \cdot \sqrt c$ .

Теорема Фробениуса

Пусть $n$ — простое, символ Якоби $\legendre{a}{n} = -1$ и $z \in \ZZ_n [\sqrt c]$ , тогда

z^n \equiv \bar{z} \pmod n

Сутью теста Фробениуса является подбор подходящих коэффициентов $a$ , $b$ и $c$ . Начать проще всего с последнего. Чтобы выполнялась теорема Фробениуса, нам нужно такое $c$ , что $\legendre{c}{n} = -1$ , в качестве значения $c$ возьмём $-1$ или наименьшее простое число, удовлетворяющее условию. Если $c \le 2$ , то $z = 2 + \sqrt c$ , иначе $z = 1 + \sqrt c$ . Если $z^n \equiv \bar{z} \pmod n$ , то число простое с вероятностью $1 - 7710^{-1}$ . Несмотря на то, что тест вероятностный, на данный момент неизвестно ни одно составное число, проходящее его, и строго доказано, что таких чисел меньше $2^{60}$ не существует.

function frobenius_test(int n) -> bool:
    tuple [int, complex] z
    for int c in [-1, 2, 3, 5, 7, ...]:
        if jacobi(c, n) == -1:
            if c <= 2:
                z.first = 2
                z.second = sqrt(c)
            else:
                z.first = 1
                z.second = sqrt(c)
            if  pow(z, n) % n == !z:
                return true
            else:
                return false

Истинные тесты

Тест Люка

Мы уже выяснили, что $n-1 = 2^s \cdot d$ . Можно разложить $d$ на произведение простых множителей $d = q_1 \cdot q_2 \cdot \dotsc \cdot q_m$ . Если число $n$ простое, то $\lvert \ZZ_n ^ \times \rvert = n-1$ . В таком случае для каждого $q$ выполняется

a^{(p-1)/q} \notequiv 1 \pmod n

Если $n$ составное, то либо для него не выполняется тест Ферма, тогда мы точно знаем, что оно не простое, либо $a^{n-1} \equiv 1 \pmod n$ . Если во втором случае будет выполняться $a^{(p-1)/q} \notequiv 1 \pmod n$ и поскольку $((n-1)/q) \divides n-1$ , мы получим, что в группе есть элемент порядка $n-1$ . При этом порядок самой группы равен $\varphi(n)$ , а это меньше $n-1$ , так как число составное. То есть получается, что порядок какого-то элемента группы больше порядка самой группы, что противоречит теореме Лагранжа. Получается, что для составных чисел такое невозможно.

function lucas_test(int n) -> bool:
while select a = random uniform int [2, n-1]:
    if pow(a, n-1) % n != n-1:
        return false
    bool flag = true
    for int q in divisors(n-1):
        if pow(a, (n-1)/q) % n == 1:
            flag = false
            break
    if flag:
        return true

Преимуществом этого алгоритма является его точность, он никогда не примет составное число за простое, но тест Люка имеет два существенных недостатка: нам нужно знать делители $n-1$ и перебирать большое количество $a$ .

Тест Люка-Лемера

Одними из самых лёгких для проверки на простоту являются числа Мерсена, имеющие вид $M_p = 2^p - 1$ . Этот метод использует рекуррентную последовательность $S$ , в которой $S_j = S_{j-1}^2 - 2$ , а первый элемент равен четырём.

S = \{ 4, \, 14, \, 194, \, 37634, \, \dotsc \}

Если $n$ — простое нечётное число, то число Мерсена $M_n = 2^n - 1$ простое только когда оно делит $S_{n-1}$ . Получается, что для проверки простоты $M_n$ нам всего-то нужно проверить, делится ли $S_{n-1}$ на $M_n$ .

function lucas_lehmer_test(int n) -> bool:
    int s = 4
    int m = 2 << n - 1
    for int i = 1; i < n-1; i++:
        s = (s * s - 2) % m
    if s == 0:
        return true
    else:
        return false

Асимптотическая сложнось этого теста равна $O(n^3)$ , но при использовании алгоритмов быстрого умножения больших чисел сложность уменьшается до $O(n^2 \cdot \log n \cdot \log \log n)$

Для доказательства работы этого теста нам понадобятся последовательности Люка. Напомню, что

U_n(P, Q) = \frac{\alpha^n - \beta^n}{\alpha - \beta}\\[0.4em]V_n(P, Q) = \alpha^n + \beta^n

Где $\alpha$ и $\beta$ — это корни квадратного уравнения

x^2 - Px + Q = 0\\[0.8em]D = P^2 - 4Q\\[0.8em]\alpha = \frac{P + \sqrt D } {2} \quad \beta = \frac{P^2 - \sqrt D } {2}

Также нам понадобятся следующие свойства таких последовательностей:

$V_n ^2 - D U_n ^2 = 4Q^n$
$V_{2n} = V_n ^2 - 2Q^n \qquad U_{2n} = U_n V_n$
$\frac{V_n + U_n \sqrt D}{2} = \left( \frac{P + \sqrt D }{2} \right) ^n$
Если $P' \equiv P \pmod N$ , $Q' \equiv Q \pmod N$ , $Q \rprime N$ и $QP' = P^2 - 2Q \pmod N$ , то
$\begin{cases} Q^n V_n (P', 1) \equiv V_{2n} (P, Q) \pmod N \\ PQ^{n-1}U_n(P', 1) \equiv U_{2n}(P, Q) \pmod N \end{cases}$
Если $p$ простое, такое, что $2QD \rprime p$ , то $p \divides U_{\Phi (p)}(P, Q)$ , где $\Phi(p) = p - \legendre{\sqrt D }{p}$ , а $\legendre{\sqrt D }{p}$ — символ Лежандра.

Пусть $N = M_p$ , $P = 2$ и $Q = -2$ .

Из четвёртого свойства следует, что

2^n V_n(-4, 1) \equiv V_{2n} (2, -2) \pmod N

А по второму свойству

V_{2n}(-4, 1) = V_n ^2(-4, 1) - 2

Таким образом получаем, что

S_{p-1} \equiv V_{(N+1)/2}(-4, 1) \pmod N\\[0.8em]V_{(N+1)/2}(2, -2) \equiv 2 ^{(N+1)/4} S_{p-1} \pmod N

$D = 2^2 -4 \cdot (-2) = 12$ , поэтому если $N$ простое, то $\legendre{D}{N} = - 1$ .

Из свойств $4$ и $5$ следует, что $N$ делит $U_{N+1} = V_{(N+1)/2}(2, -2) \cdot U_{(N+1)/2}(2, -2)$

А из свойств $1$ и $2$ получаем, что

V_{N+1} = V_{(N+1)/2}^2 - 2 \cdot (-2)^{(N+1)/2} \equiv 8 +4 = 12 \pmod N

По третьему свойству

V_{N+1} \equiv 2(1 + \sqrt 3 )^{N+1} \equiv 2(1-3) = -4 \pmod N

И в итоге получаем, что $N \divides S_{p-1}$ . Таким образом мы доказали необходимость условий. Но, чтобы называть тест детерменированным, нам нужно также доказать достаточность.

Если $N \divides S_{p-1}$ , то оно делит и $V_{(n+1)/2}$ . По первому свойству $N \rprime U_{(N+1)/2}$ , а по второму $N \divides U_{N+1}$ . Тогда каждый простой делитель $N$ можно представить как $\pm 1 + k \cdot 2^p$ , это больше, чем $\sqrt N$ , а значит, что $N = M_p$ простое.