Википедия

Тест Люка — Лемера — Ризеля: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
мНет описания правки
мНет описания правки
Строка 1:
'''Тест Люка — Лемера — Ризеля ''' (''LLR'') — [[тест простоты]] для чисел вида <math>N = k \cdot 2^n-1</math> с <math>2^n > k</math>
(подмножество <math>3 \cdot 2^n - 1</math> таких чисел называется [[Числа Сабита|числами Сабита]]).
Был разработан [[Ханс Ризель|Хансом Ризелем]] и базируется на [[Тест Люка — Лемера|тесте Люка — Лемера]], является самым быстрым детерминированным алгоритмом для чисел такого вида. Для проверки простоты похожих на эти чисел [[Число Прота|чисел Прота]] — <math>N = k \cdot 2^n+1</math> используется либо [[Теорема Прота]] ([[Лас-Вегас (алгоритм)|вероятностный алгоритм]]), либо один из детерминированных алгоритмов, описанных Брилхартом, Лемером и Селфриджом в 1975{{sfn| Brillhart, Lehmer, Selfridge|1975}}{{Уточнить}}<!--а причём тут числа Прота, когда тест про числа Сабита?-->.
 
== Алгоритм ==
Источник — https://ru.wikipedia.org/wiki/Тест_Люка_—_Лемера_—_Ризеля