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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

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

Тест[править | править вики-текст]

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

Пусть q — простое число, причем q\geq{3}. Определим последовательность L_n следующим образом:

L_0=4,
L_{n+1}={L_n}^2-2.

Тогда M_q — простое тогда и только тогда, когда L_{q-2}\equiv 0\pmod{M_q}.


Для установления простоты 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 является простым тогда и только тогда, когда число q простое, и вычет Люка — Лемера равен нулю.

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

Вычислительная сложность[править | править вики-текст]

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

Примеры[править | править вики-текст]

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

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

Следовательно, число 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.

Доказательство теоремы основано на свойствах последовательностей Люка U_n=U_n(4,1) и V_n=V_n(4,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} = \tfrac{1}{\sqrt{12}}((2 + \sqrt{3})^{n} - (2 - \sqrt{3})^{n})
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\pmod{p^e}, то U_{np}\equiv0\pmod{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}\pmod{p^{e+1}}, в то время как U_{2n+1}=U_{n+1}^2-U_{n}^2\equiv{a}^2\pmod{p^{e+1}}.

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

U_{3n}=U_{2n+1}U_{n}-U_{2n}U_{n-1}\equiv(3a^2)U_{n}\pmod{p^{e+1}} и U_{3n+1}=U_{2n+1}U_{n+1}-U_{2n}U_{n}\equiv{a}^3\pmod{p^{e+1}}.

Иначе говоря,

U_{kn}\equiv(ka^{k-1})U_{n}\pmod{p^{e+1}} и U_{kn+1}\equiv{a^k}\pmod{p^{e+1}},

откуда следует утверждение леммы, если взять k=p.

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

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

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

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

Если p\neq3 теорема Ферма утверждает, что 3^{p-1}\equiv1\pmod{p}. Поэтому (3^{(p-1)/2}-1)(3^{(p-1)/2}+1)\equiv0\pmod{p}, то есть 3^{(p-1)/2}\equiv\pm1\pmod{p}. Если U_{p}\equiv{-1}\pmod{p}, то

U_{p+1}=4U_{p}-U_{p-1}=4U_{p}+V_{p}-U_{p+1}\equiv{-U_{p+1}}\pmod{p},

то есть U_{p+1}=0\pmod{p}. Таким же способом получим, что U_{p-1}=0\pmod{p}, если U_{p}=1. Мы доказали, что для любого простого числа, существует целое число \mid\epsilon(p)\mid\leq1 такое, что U_{p+\epsilon(p)}=0\pmod{p}.

Лемма: Если N — положительное целое число, и m=m(N) — наименьшее число такое, что U_{m(N)}\equiv 0\pmod{N}, то мы имеем:

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

Доказательство: Заметим, что последовательность U_n, U_{n+1}, U_{n+2},... совпадает с последовательностью aU_0,aU_1,aU_2,... по модулю 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\pmod{2^q-1}
U_{2^{q-2}}\not\equiv0\pmod{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\equiv (-1)^q-1=-2\pmod{3}, q — простое по условию. Используя ранее доказанные леммы, получим U_t\equiv0\pmod{2^q-1}, где

t=\mathrm{lcm}({p_1}^{e_1-1}(p_1+\epsilon_1),\dots,{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\pmod{n}. Для этого достаточно показать, что V_{2^q-1}\equiv{-2}\pmod{n}, так как V_{2^q-1}=(V_{2^q-2}-2)^2.

V_{2^q-1}=\left(\frac{\sqrt{2}+\sqrt{6}}2\right)^{n+1}+\left(\frac{\sqrt{2}-\sqrt{6}}2\right)^{n+1}=2^{-n}\sum_{k} \binom{n+1}{2k}{\sqrt{2}}^{n+1-2k}\sqrt{6}^{2k}=2^{(1-n)/2}\sum_{k} \binom{n+1}{2k}3^k.

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

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

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

Псевдокод[править | править вики-текст]

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.[4] Также существует более общий вариант — тест Люка, который применим для любого натурального числа N, если известно разложение на простые множители числа N-1.

Применения[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

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

Литература[править | править вики-текст]