- Тест Люка — Лемера
-
Тест Люка — Лемера
Тест Люка́ — Ле́мера — эффективный тест простоты для чисел Мерсенна. Этот тест был предложен Люка в 1878 году и в 1930 году усовершенствован Лемером (Lehmer).
Тест Люка — Лемера базируется на том наблюдении, что простота числа Мерсенна Mp = 2p - 1 влечёт простоту числа p, и следующем утверждении:
Для простого числа число Mp является простым тогда и только тогда, когда оно делит число Lp - 1, где числа Lk определяются рекуррентным соотношением: .
Для установления простоты Mp последовательность чисел достаточно вычислять по модулю числа Mp (т. е. вычислять не сами числа Lk, длина которых растёт экспоненциально; а остатки от деления Lk на Mp, длина которых ограничена p битами). Последнее число в этой последовательности Lp - 1mod Mp называется вычетом Люка — Лемера. Таким образом, число Мерсенна Mp является простым тогда и только тогда, когда число p простое, и вычет Люка — Лемера равен нулю.Возможными значениями L1 являются: 4, 10, 52, 724, 970, ... (последовательность A018844 в OEIS)
Благодаря тесту Люка — Лемера простые числа Мерсенна удерживают лидерство как самые большие известные простые числа. Именно тест Люка — Лемера лежит в основе проекта распределённых вычислений GIMPS, занимающимся поиском новых простых чисел Мерсенна.
Литература
- Weisstein, Eric W. Lucas-Lehmer Test(англ.) на сайте Wolfram MathWorld.
- А.Н.Рудаков Числа Фибоначчи и простота числа 2127-1 // Математическое Просвещение. — 2000. — В. 4 (третья серия).
Wikimedia Foundation. 2010.
Тест Люка — Тест Люка Лемера эффективный тест простоты для чисел Мерсенна. Благодаря этому тесту самые большие простые числа всегда были числами Мерсенна даже задолго до появления компьютеров.[1] Содержание 1 История 2 Тест 3 … Википедия
Тест Люка-Лемера — … Википедия
Тест Люка—Лемера — … Википедия
Тест простоты — Тест простоты алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… … Википедия
Тест — (от слова англ. test) «испытание», «проверка» это метод изучения глубинных процессов деятельности человека, посредством его высказываний или оценок факторов функционирования системы управления Содержание 1 Программирование 2 Математика … Википедия
Люка, Франсуа Эдуард Анатоль — Эдуард Люка Édouard Lucas Дата рождения … Википедия
Люка Франсуа Эдуард Анатоль — Эдуард Люка Édouard Lucas Дата рождения: 4 апреля 1842 Место рождения: Амьен Дата смерти: 8 октября 1891 Научная сфера: математика … Википедия
Тест (значения) — Может, вы искали ?Тест (от слова en. test) испытание, проверка, анализ. Программирование * Тестирование программного обеспечения * Тест Тьюринга * Бета тестирование Тесты в биологических и биохимических исследованиях * Тест на ВИЧ *… … Википедия
Тест Агравала — В информатике тест Агравала Каяла Саксены (или тест AKS) это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёным Маниндрой Агравалом (англ.) и его двумя студентами Нираджем Каялом (англ … Википедия
Тест Ферма — Тест простоты Ферма в теории чисел это тест простоты натурального числа n, основанный на малой теореме Ферма. Содержание Если n простое число, то оно удовлетворяет сравнению для любого a, где n не делит a. Выполнение сравнения… … Википедия