Тест Люка

Тест Люка — Лемера — эффективный тест простоты для чисел Мерсенна. Благодаря этому тесту самые большие простые числа всегда были числами Мерсенна даже задолго до появления компьютеров.^[1]

История

Тест был предложен французским математиком Люка в 1878 году и дополнен американским математиком Лемером в 1930 году. Полученный тест носит имя двух ученых, которые совместно открыли его, даже не встречаясь при жизни. В 1952 году Робинсон при поддержке Лемера провел вычисления на компьютере SWAC с использованием теста Люка - Лемера, результатом которого стало открытие простых чисел $M_{521}$,$M_{607}$. Позднее, в этом же году были открыты $M_{1279}$, $M_{2203}$, $M_{2281}$.^[2]

Тест

Тест Люка — Лемера базируется на том наблюдении, что простота числа Мерсенна $M_q = 2^q - 1$ влечёт простоту числа $q$, и следующем утверждении:

Пусть $q$ - простое число, причем $q\geq{3}$. Определим последовательность $L_n$ следующим образом: $L_0=4$ $L_{n+1}={L_n}^2-2\mod{2^q-1}$ Тогда $2^q-1$ - простое тогда и только тогда, когда $L_{q-2}=0\mod{2^q-1}$

Для установления простоты $M_p$ последовательность чисел $L_0, L_2, \ldots, L_{q-2}$ вычисляется по модулю числа $M_q$ (т. е. вычисляются не сами числа $L_k$, длина которых растёт экспоненциально; а остатки от деления $L_k$ на $M_q$, длина которых ограничена p битами). Последнее число в этой последовательности $L_{q-2} \bmod M_q$ называется вычетом Люка — Лемера. Таким образом, число Мерсенна $M_q$ является простым тогда и только тогда, когда число $p$ простое, и вычет Люка — Лемера равен нулю.

Возможными значениями $L_0$ являются: 4, 10, 52, 724, 970, 10084, … (последовательность A018844 в OEIS)

Сложность

Сложность теста для числа $n=2^{q}-1$ равна $O((\log{n})^3)$^[3] , так как в процессе выполнения теста мы производим $O(q)$ возведений в квадрат и вычитаний по модулю $n$. Длина $n$ - $q$ бит, причем самый простой алгоритм умножения чисел имеет сложность $O(q^2)$. Для ускорения теста следует использовать алгоритмы быстрого умножения больших целых чисел, например, метод умножения Шёнхаге — Штрассена. Сложность в таком случае составит $O(q^{2}\log{q}\log{\log{q}})$.

Примеры

Рассмотрим выполнение теста для числа Мерсенна $M_{13}=8191$.

$L_0=4\mod{8191}$
$L_1=4^2-2=14\mod{8191}$
$L_2=14^2-2=194\mod{8191}$
$L_3=194^2-2=4870\mod{8191}$
$L_4=4870^2-2=3953\mod{8191}$
$L_5=3953^2-2=5970\mod{8191}$
$L_6=5970^2-2=1857\mod{8191}$
$L_7=1857^2-2=36\mod{8191}$
$L_8=36^2-2=1294\mod{8191}$
$L_9=1294^2-2=3470\mod{8191}$
$L_{10}=3470^2-2=128\mod{8191}$
$L_{11}=128^2-2=0\mod{8191}$

Следовательно, число $M_{13}=8191$ - простое.

Доказательство

Теорема: Пусть $q$ - простое число, причем $q\geq{3}$. Определим последовательность $L_n$ следующим образом:
$L_0=4$
$L_{n+1}={L_n}^2-2\mod{2^q-1}$
Тогда $2^q-1$ - простое тогда и только тогда, когда $L_{q-2}=0\mod{2^q-1}$.
Доказательство теоремы основано на простейших принципах теории чисел. Исследуем некоторые свойства рекуррентных последовательностей. Положим, что

$U_0 = 0, U_1 = 1, U_{n+1} = 4U_{n} - U_{n-1}$

$V_0 = 2, V_1 = 4, V_{n+1} = 4V_{n} - V_{n-1}$

Следующие свойства доказываются по индукции:

$V_{n} = U_{n+1} - U_{n-1}$

$U_{n} = ((2 + \sqrt{3})^{n} - (2 - \sqrt{3})^{n}) / \sqrt{12}$

$V_{n} = (2 + \sqrt{3})^{n} - (2 - \sqrt{3})^{n}$

$U_{m+n} = U_{m}U_{n+1} - U_{m-1}U_{n}$

Лемма: Пусть $p$ - простое и $e \geq 1$, тогда справедливо следующее утверждение. Если $U_{n}\equiv0\mod{p^e}$, то $U_{np}\equiv0\mod{p^{e+1}}$.
Доказательство леммы: Положим $U_{n}=bp^e$, $U_{n+1}=a$. Используем выше описанные свойства, чтобы получить значения для $U_{2n}$ и $U_{2n+1}$:

$U_{2n}=bp^{e}(2a-4bp^e)\equiv2aU_{n}\mod{p^{e+1}}$, в то время как $U_{2n+1}=U_{n+1}^2-U_{n}^2\equiv{a}^2\mod{p^{e+1}}$.

Таким же способом получим:

$U_{3n}=U_{2n+1}U_{n}-U_{2n}U_{n-1}\equiv(3a^2)U_{n}\mod{p^{e+1}}$ и $U_{3n+1}=U_{2n+1}U_{n+1}-U_{2n}U_{n}\equiv{a}^3\mod{p^{e+1}}$. Иначе говоря, $U_{kn}\equiv(ka^{k-1})U_{n}\mod{p^{e+1}}$ и $U_{kn+1}\equiv{a^k}\mod{p^{e+1}}$, откуда следует утверждение леммы, если взять $k=p$.

Далее, раскроем выражение последовательностей по биному Ньютона:

$U_{n}=\sum_{k} {n \choose 2k+1}2^{n-2k-1}3^{k}$, $V_{n}=\sum_{k} {n \choose 2k}2^{n-2k+1}3^{k}$

Теперь, если мы положим $n=p$, где $p$- простое число, большее 2, и учтем, что${n \choose k}$ кратно $p$ за исключением тех случаев, когда $k=0$ и $k=n$, мы получим:

$U_{p}\equiv3^{(p-1)/2}\mod{p}$, $V_p\equiv4\mod{p}$.

Если $p\neq3$ теорема Ферма утверждает, что $3^{p-1}\equiv1\mod{p}$. Поэтому $(3^{(p-1)/2}-1)(3^{(p-1)/2}+1)\equiv0\mod{p}$, то есть $3^{(p-1)/2}\equiv\pm1\mod{p}$. Если $U_{p}\equiv{-1}\mod{p}$, то $U_{p+1}=4U_{p}-U_{p-1}=4U_{p}+V_{p}-U_{p+1}\equiv{-U_{p+1}}\mod{p}$, то есть $U_{p+1}=0\mod{p}$. Таким же способом получим, что $U_{p-1}=0\mod{p}$, если $U_{p}=1$. Мы доказали, что для любого простого числа, существует целое число $\mid\epsilon(p)\mid\leq1$ такое, что $U_{p+\epsilon(p)}=0\mod{p}$.
Лемма: Если $N$ - положительное целое число, и $m=m(N)$ - наименьшее число такое, что $U_{m(N)}=0\mod{N}$, то мы имеем:

$U_n=0\mod{N}$ тогда и только тогда, когда $n$ кратно $m(N)$.

Доказательство: Заметим, что последовательность $U_n,U_{n+1},U_{n+2},...$ совпадает с последовательностью $aU_0,aU_1,aU_2,...$ по $\mod{M}$, где $a=U_{m+1}\mod{N}$ - взаимно простое с $N$, так как :$\gcd{(U_n,U_{n+1})}=1$.
Доказательство теоремы: по индукции:

$L_n=V_{2^n}\mod{2^q-1}$.

Более того, из $2U_{n+1}=4U_n+V_n$ следует, что $\gcd{(U_n,V_n)}\leq2$. Отсюда следует, что $U_n$ и $V_n$ не имеют общих нечетных делителей. Если $L_{q-2}=0$, то для $U_{2^{q-1}}$ и $U_{2^{q-2}}$ можем записать

$U_{2^{q-1}}=U_{2^{q-2}}V_{2^{q-2}}\equiv0\mod{2^q-1}$

$U_{2^{q-2}}\not\equiv0\mod{2^q-1}$

Теперь, если $m=m(2^q-1)$, то $m$ должно быть делителем числа $2^{q-2}$, но не должно делить $2^{q-2}$, поэтому $m=2^{q-1}$. Докажем, что $n=2^{q}-1$. Пусть $n={p_1}^e_1...{p_r}^e_r$. Числа $p_j$ больше 3, так как $n$ нечетное и выполняется $n=2^q-1=(-1)^q-1=-2\mod{3}$, $q$ - простое по условию. Используя ранее доказанные леммы, получим $U_t\equiv0\mod{2^q-1}$, где

$t=lcm({p_1}^{e_1-1}(p_1+\epsilon_1),...,{p_r}^{e_r-1}(p_r+\epsilon_r))$

где $\epsilon_j=\pm1$. Отсюда следует, что $t$ кратно $m=2^q-1$. Положим $n_0=\prod^r_{j=1}{p_j}^{e_j-1}(p_j+\epsilon_j)$; $n_0\leq\prod^r_{j=1}{p_j}^{e_j-1}(p_j+1/5p_j)=(6/5)^rn$. Так как $p_j+\epsilon_j$ - четное, $t\leq{n_0}/2^{r-1}$. Используем ранее доказанные факты и получим $m\leq{t}\leq2(3/5)^{r}m<4(3/5)^rm<3m$; следовательно $r\leq2$ и $t=m$ либо $t=2m$. Заметим, что $t$ - степень двойки. Отсюда следует, что $e_1=1$ и $e_r=1$. Если $n$ - составное, то должно быть $n=2^q-1=(2^k+1)(2^l-1)$, где $2^k+1$ и $2^l-1$ - простые числа. Дальнейшее разложение на простые числа, если $q$ - нечетное, невозможно, поэтому $n$ - простое.

Наоборот, предположим, что $n=2^q-1$ - простое. Покажем, что $V_{2^q-2}\equiv0\mod{n}$. Для этого достаточно показать, что $V_{2^q-1}\equiv{-2}\mod{n}$, так как $V_{2^q-1}=(V_{2^q-2}-2)^2$.

$V_{2^q-1}=((\sqrt{2}+\sqrt{6})/2)^{n+1}+((\sqrt{2}-\sqrt{6})/2)^{n+1}=2^{-n}\sum_{k}{n+1 \choose 2k}{\sqrt{2}}^{n+1-2k}\sqrt{6}^{2k}=2^{(1-n)/2}\sum_{k}{n+1 \choose 2k}3^k$

Так как $n$ - простое, то биномиальный коэффициент ${n+1 \choose 2k}={n \choose 2k}+{n \choose 2k-1}$ делится на $n$ кроме тех случаев, когда $k=0$ или $k=(n+1)/2$; следовательно

$2^{(n-1)/2}V_{2^q-1}\equiv{1+3^{(n+1)/2}}\mod{n}$.

Здесь $2\equiv(2^{(q+1)/2})^2\mod{n}$, поэтому $2^{(n-1)/2}\equiv{(2^{(q+1)/2})}^{n-1}\equiv1\mod{n}$ по теореме Ферма. Наконец, используя простейший случай квадратичного закона взаимности, покажем, что $3^{(n-1)/2}\equiv{-1}\mod{n}$, так как $n\mod{3}=1$ и $n\mod{4}=3$. Это означает, что $V_{2^q-1}\equiv{-2}$, так что $V_{2^q-2}\equiv0$. ^[4]

Псевдокод

Lucas–Lehmer(p)
    var s = 4
    var M = 2p — 1
    repeat p — 2 times:
        s = ((s × s) — 2) mod M
    if s = 0 return PRIME else return COMPOSITE

Модификации

Для чисел вида $k2^n-1$, где $2^n>k$ существует модификация данного теста, разработанная Хансом Ризелем (швед. Hans Riesel). Возможно обобщение теста для чисел вида $A2^{2n}+B2^{n}-1$.^[5] Также существует более общий вариант - тест Люка, который применим для любого натурального числа $N$, если известно разложение на простые множители числа $N-1$.

Применения

Благодаря тесту Люка — Лемера простые числа Мерсенна удерживают лидерство как самые большие известные простые числа. Именно тест Люка — Лемера лежит в основе проекта распределённых вычислений GIMPS, занимающимся поиском новых простых чисел Мерсенна.

См.Также

• Тест простоты
• Тест простоты Люка
• Числа Мерсенна
• Тест Люка - Лемера - Ризеля

Примечания

1. ↑ Paulo Ribenboim The Little Book of Bigger Primes. — Springer. — 2004. — С. 78. — ISBN 978-0387201696
2. ↑ Paulo Ribenboim The Little Book of Bigger Primes. — Springer. — 2004. — С. 79. — ISBN 978-0387201696
3. ↑ Eric Bach; Jeffrey Shallit Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 275. — ISBN 978-0262024051
4. ↑ Donald E. Knuth The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — 3 (3 edition). — Addison-Wesley Professional, 1997. — С. 2. — 392 с. — ISBN 978-0201896848
5. ↑ H. C. Williams A class of primality tests for trinomials which includes the Lucas-Lehmer test.  (англ.). Архивировано из первоисточника 23 декабря 2012. Проверено 28 ноября 2012.

Литература

• Weisstein, Eric W. Lucas-Lehmer Test (англ.) на сайте Wolfram MathWorld.
• А.Н.Рудаков Числа Фибоначчи и простота числа 2¹²⁷-1 // Математическое Просвещение. — 2000. — В. 4 (третья серия).
• Donald E. Knuth The Art of Computer Programming, Volume 2: Seminumerical Algorithms. — Addison-Wesley Professional. — 1997. — С. 389-394. — ISBN 978-0201896848
• Paulo Ribenboim The Little Book of Bigger Primes. — Springer. — 2004. — С. 75-80. — ISBN 978-0387201696
• Eric Bach; Jeffrey Shallit Algorithmic Number Theory, Vol. 1: Efficient Algorithms. — The MIT Press, 1996. — С. 273-275. — ISBN 978-0262024051