Тест Люка

Тест Люка

Тест Люка — Лемера — эффективный тест простоты для чисел Мерсенна. Благодаря этому тесту самые большие простые числа всегда были числами Мерсенна даже задолго до появления компьютеров.[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.

Литература



Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Тест Люка" в других словарях:

  • Тест Люка — Лемера — эффективный тест простоты для чисел Мерсенна. Этот тест был предложен Люка в 1878 году и в 1930 году усовершенствован Лемером (Lehmer). Тест Люка Лемера базируется на том наблюдении, что простота числа Мерсенна Mp = 2p 1 влечёт простоту …   Википедия

  • Тест Люка-Лемера — …   Википедия

  • Тест Люка—Лемера — …   Википедия

  • Тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… …   Википедия

  • Тест — (от слова англ. test)  «испытание», «проверка» это метод изучения глубинных процессов деятельности человека, посредством его высказываний или оценок факторов функционирования системы управления Содержание 1 Программирование 2 Математика …   Википедия

  • Люка, Франсуа Эдуард Анатоль — Эдуард Люка Édouard Lucas Дата рождения …   Википедия

  • Люка Франсуа Эдуард Анатоль — Эдуард Люка Édouard Lucas Дата рождения: 4 апреля 1842 Место рождения: Амьен Дата смерти: 8 октября 1891 Научная сфера: математика …   Википедия

  • Тест (значения) — Может, вы искали ?Тест (от слова en. test) испытание, проверка, анализ. Программирование * Тестирование программного обеспечения * Тест Тьюринга * Бета тестирование Тесты в биологических и биохимических исследованиях * Тест на ВИЧ *… …   Википедия

  • Тест Агравала — В информатике тест Агравала  Каяла  Саксены (или тест AKS)  это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёным Маниндрой Агравалом (англ.) и его двумя студентами Нираджем Каялом (англ …   Википедия

  • Тест Пепина — тест простоты для чисел Ферма. Описание Псевдокод ОТ ДО ВЫП ЕСЛИ ТО ВОЗВРАТ « …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»