Тест Люка — Лемера — Ризеля: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Bezik (обсуждение | вклад) м →Механизм теста: снял одну из пометок |
Jumpow (обсуждение | вклад) мНет описания правки |
||
Строка 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}}{{Уточнить}}<!--а причём тут числа Прота, когда тест про числа Сабита?-->.
== Алгоритм ==
Строка 28:
В тестах, подобных тестам Люка, для числа <math>N</math> используется мультипликативная группа квадратичного расширения целых по модулю <math>N</math>. Если <math>N</math> — простое, порядок мультипликативной группы равен <math>N^2-1</math> и она имеет подгруппу порядка <math>N+1</math>, для целей теста ищется [[Порождающее множество группы|порождающее множество]] этой подгруппы.
Следуя модели теста Люка — Лемера, положим <math>u_i = a^{2^i} + a^{-2^i}</math> и получим по индукции <math>u_i = u_{i-1}^2 - 2</math>.
| |||