Тест Люка — Лемера — Ризеля: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Liasmi (обсуждение | вклад) стилевые правки (был), оформление, проверка орф.и пункт. |
Stannic (обсуждение | вклад) м оформление |
||
Строка 1:
'''Тест Люка — Лемера — Ризеля ''' (''LLR'') — [[тест простоты]] для чисел вида <math>N = k \cdot 2^n-1</math> с <math>2^n > k</math>
(подмножество <math>3 \cdot 2^n - 1</math> таких чисел называется [[Числа Сабита|числами Сабита]]).
Разработан [[Ханс Ризель|Хансом Ризелем]] и базируется на [[Тест Люка — Лемера|тесте Люка — Лемера]], является самым быстрым детерминированным алгоритмом для чисел такого вида<ref>Для проверки простоты похожих на эти [[Число Прота|чисел Прота]]
== Алгоритм ==
Алгоритм очень похож на тест Люка
: <math>u_i = u_{i-1}^2-2</math>.
<math>N</math> является простым в том и только в том случае, когда оно делит
== Поиск стартового значения ==
* Случай <math>k = 1</math>. Если <math>n</math>
* Случай <math>k = 4</math>. Значение <math>u_0 = 5778</math> можно использовать для всех <math>n \equiv 0, 3 \pmod 4</math>n ≡ 0, 3 (mod 4).
* Если <math>k \equiv 1,5 \pmod 6</math> и <math>N</math> не делится на 3, можно использовать значение <math>u_0 = (2+\sqrt{3})^k+(2-\sqrt{3})^k</math>.
* В остальных случаях <math>k</math> делится на 3 и выбрать правильное стартовое значение ''u''<sub>0</sub> значительно труднее.
| |||